Теория структурной сложности

В теории вычислительной сложности информатики , а не вычислительной сложности теория структурной сложности или просто структурная сложность — это изучение классов сложности отдельных задач и алгоритмов. Оно предполагает исследование как внутренних структур различных классов сложности, так и отношений между разными классами сложности. ^[1]

История [ править ]

Теория возникла в результате (пока безуспешных) попыток решить первый и до сих пор самый важный вопрос такого рода — проблему P = NP . Большая часть исследований проводится на основе предположения о том, что P не равно NP, и на более далеко идущей гипотезе о том, что полиномиальная временная иерархия классов сложности бесконечна. ^[1]

Важные результаты [ править ]

Теорема о сжатии [ править ]

Теорема о сжатии — важная теорема о сложности вычислимых функций .

Теорема утверждает, что не существует наибольшего класса сложности с вычислимой границей, который содержал бы все вычислимые функции.

пространственной о Теоремы иерархии

Теоремы о пространственной иерархии представляют собой результаты разделения, которые показывают, что как детерминированные, так и недетерминированные машины могут решать больше задач в (асимптотически) большем пространстве при соблюдении определенных условий. Например, детерминированная машина Тьюринга может решить больше задач принятия решений в пространстве n log n, чем в пространстве n . Несколько более слабыми аналогичными теоремами для времени являются теоремы об иерархии времени .

времени иерархии Теоремы об

Теоремы об иерархии времени являются важными утверждениями об ограниченных по времени вычислениях на машинах Тьюринга . Неофициально эти теоремы утверждают, что, если потратить больше времени, машина Тьюринга сможет решить больше задач. Например, есть задачи, которые можно решить с помощью n ² время, но не n раз.

– Вазирани Теорема Валианта

Теорема Валианта–Вазирани — теорема теории сложности вычислений . Это доказали Лесли Валиант и Виджай Вазирани в их статье под названием «NP так же просто, как обнаружить уникальные решения», опубликованной в 1986 году. ^[2]Теорема утверждает, что если существует алгоритм с полиномиальным временем для Unambiguous-SAT , то NP = RP .Доказательство основано на лемме об изоляции Малмули-Вазирани , которая впоследствии использовалась для ряда важных приложений в теоретической информатике .

Теорема Сипсера–Лаутмана [ править ]

Теорема Сипсера-Лаутенанна или теорема Сипсера-Гача-Лаутенмана утверждает, что время вероятностного полинома с ограниченной ошибкой (BPP) содержится в иерархии полиномиального времени , а точнее, Σ ₂ ∩ Π ₂ .

Теорема Савича [ править ]

Теорема Сэвича, доказанная Уолтером Сэвичем в 1970 году, устанавливает связь между детерминированной и недетерминированной сложностью пространства . Он утверждает, что для любой функции $f\in \Omega (\log(n))$ ,

{\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).

Теорема Тоды [ править ]

Теорема Тоды — это результат, который был доказан Сейносуке Тодой в его статье «PP столь же труден, как иерархия полиномиального времени» (1991) и получил премию Гёделя 1998 года . Теорема утверждает, что вся полиномиальная иерархия PH содержится в P ^ПП; это подразумевает тесно связанное утверждение о том, что PH содержится в P ^#П.

Теорема Иммермана–Селепшени [ править ]

Теорема Иммермана-Селепшени была независимо доказана Нилом Иммерманом и Робертом Селепшени в 1987 году, за что они разделили премию Гёделя 1995 года . В своей общей форме теорема утверждает, что NSPACE ( s ( n )) = co-NSPACE( s ( n )) для любой функции s ( n ) ≥ log n . Результат эквивалентно формулируется как NL = co-NL; хотя это частный случай, когда s ( n ) = log n , из него следует общая теорема с помощью стандартного аргумента заполнения ^{[ нужна ссылка ]}. Результат решил вторую проблему LBA .

Темы исследований [ править ]

К основным направлениям исследований в этой области относятся: ^[1]

изучение последствий, вытекающих из различных нерешенных проблем, касающихся классов сложности
изучение различных типов ресурсо-ограниченных редукций и соответствующих полных языков
изучение последствий различных ограничений и механизмов хранения и доступа к данным

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с Юрис Хартманис , «Новые достижения в теории структурной сложности» (приглашенная лекция), Учеб. 15-й Международный коллоквиум по автоматам, языкам и программированию , 1988 г. (ICALP 88), Конспекты лекций по информатике , том. 317 (1988), стр. 271–286.
^ Валиант, Л.; Вазирани, В. (1986). «NP — это так же просто, как найти уникальные решения» (PDF) . Теоретическая информатика . 47 : 85–93. дои : 10.1016/0304-3975(86)90135-0 .

[jha-1] Jump up to: Перейти обратно: ^а ^б ^с Юрис Хартманис , «Новые достижения в теории структурной сложности» (приглашенная лекция), Учеб. 15-й Международный коллоквиум по автоматам, языкам и программированию , 1988 г. (ICALP 88), Конспекты лекций по информатике , том. 317 (1988), стр. 271–286.

[2] Валиант, Л.; Вазирани, В. (1986). «NP — это так же просто, как найти уникальные решения» (PDF) . Теоретическая информатика . 47 : 85–93. дои : 10.1016/0304-3975(86)90135-0 .

[1]

[2]