Оглавление
Теория структурной сложности
-
Основы теории структурной сложности
- Теория структурной сложности изучает классы сложности, а не вычислительную сложность отдельных задач.
- Исследует внутренние структуры и отношения между классами сложности.
-
Исторический контекст
- Возникла в результате попыток решить проблему P = NP.
- Исследования основаны на предположении о неравенстве P и NP и гипотезе о бесконечности иерархии классов сложности.
-
Важные результаты
- Теорема о сжатии: не существует самого большого класса сложности, содержащего все вычислимые функции.
- Теоремы о пространственной и временной иерархии: показывают, что машины Тьюринга могут решать больше задач при увеличении пространства или времени.
- Теорема Валианта-Вазирани: если существует алгоритм с полиномиальным временем для SAT, то NP = RP.
- Теорема Зипсера-Лаутемана: BPP содержится в иерархии полиномиального времени.
- Теорема Савича: детерминированная и недетерминированная сложность пространства связаны.
- Теорема Тоды: вся полиномиальная иерархия содержится в PPP.
- Теорема Иммермана-Шелепчени: NSPACE(s(n)) = co-NSPACE(s(n)) для любой функции s(n) ≥ log n.
-
Направления исследований
- Изучение последствий нерешенных проблем, связанных с классами сложности.
- Исследование сокращений, связанных с ограниченными ресурсами и полными языками.
- Изучение последствий ограничений и механизмов хранения и доступа к данным.
Полный текст статьи: