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

Эта страница посвящена теории структурной сложности в теории вычислительной сложности информатики. Для структурной сложности в прикладной математике см. Структурную сложность (прикладная математика) .

Наглядное представление иерархии полиномиального времени. Стрелки обозначают включение.

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

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

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

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

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

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

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

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

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

Теоремы об иерархии времени [ править ]

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

Теорема Вэлианта – Вазирани [ править ]

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

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

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

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

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

${\ Displaystyle {\ mathsf {NSPACE}} \ влево (е \ влево (п \ вправо) \ вправо) \ substeq {\ mathsf {DSPACE}} \ влево (\ влево (е \ влево (п \ вправо) \ вправо) ^ {2} \ right).}$

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

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

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

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

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

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

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

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