PSPACE-полный - PSPACE-complete

В теория сложности вычислений, а проблема решения является PSPACE-полный если ее можно решить, используя объем памяти, полиномиальный от входной длины (полиномиальное пространство ) и если любая другая задача, которую можно решить в полиномиальном пространстве, может быть преобразован в него за полиномиальное время. Проблемы, которые являются PSPACE-complete, можно рассматривать как самые сложные проблемы в PSPACE, потому что решение любой такой проблемы можно легко использовать для решения любой другой проблемы в PSPACE.

Многие подозревают, что проблемы PSPACE-complete не входят в более известные классы сложности. п и НП, но это не известно.^[1] Известно, что они лежат вне класса NC (класс задач с высокоэффективным параллельные алгоритмы ), потому что проблемы в NC может быть решена в объеме многочлена от логарифм размера ввода, а класс задач, решаемых на таком небольшом пространстве, строго содержится в PSPACE посредством теорема пространственной иерархии.

Примеры

Регулярные выражения и автоматы

Учитывая регулярное выражение р, определение того, генерирует ли он каждую строку в своем алфавите, является PSPACE-полным.^[2]

Связанный результат состоит в том, что класс языков, распознаваемых с нулевой ошибкой автоматами с двусторонней бесконечной случайной лентой, равен недетерминированное линейное пространство. Это справедливо как для двустороннего, так и для многопроходного одностороннего доступа к входу. Проверка того, принимает ли автомат (с двусторонней бесконечной случайной лентой) слово с нулевой ошибкой, завершается NSPACE (O (kn)), где n - размер ввода, а k - количество состояний.

Контекстно-зависимые грамматики

Первый известный PSPACE-полная проблема была проблема со словом за детерминированный контекстно-зависимые грамматики. В проблеме слов для контекстно-зависимых грамматик каждому дается набор грамматических преобразований, которые могут увеличивать, но не могут уменьшаться, длину предложения, и он хочет определить, может ли данное предложение быть произведено этими преобразованиями. Техническое условие «детерминизма» (подразумевающее примерно то, что каждое преобразование делает очевидным, что оно было использовано) гарантирует, что этот процесс может быть решен в полиномиальном пространстве, и Курода (1964) показал, что каждая (возможно, недетерминированная) программа, вычислимая в линейное пространство может быть преобразован в синтаксический анализ контекстно-зависимой грамматики таким образом, чтобы сохранить детерминизм.^[3] В 1970 г. Теорема савича показал, что PSPACE закрыт недетерминизмом, подразумевая, что даже недетерминированные контекстно-зависимые грамматики находятся в PSPACE.

Количественные булевы формулы

В настоящее время архетипическая проблема PSPACE-complete обычно рассматривается как квантифицированная задача булевой формулы (обычно сокращенно QBF или TQBF; T означает «истина»), обобщение первого известного НП-полный проблема, Проблема логической выполнимости (СИДЕЛ). Проблема выполнимости - это проблема того, есть ли присвоения ценности истины к переменным, которые делают логическое выражение истинным.^[4] Например, одним из примеров SAT будет вопрос о том, верно ли следующее:

${ Displaystyle существует х_ {1} , существует х_ {2} , существует х_ {3} , существует х_ {4} :( х_ {1} lor neg x_ {3} lor x_ {4}) land ( neg x_ {2} lor x_ {3} lor neg x_ {4})}$

Проблема количественной булевой формулы отличается тем, что допускает как универсальную, так и экзистенциальную количественную оценку значений переменных:

${ Displaystyle существует x_ {1} , forall x_ {2} , exists x_ {3} , forall x_ {4} :( x_ {1} lor neg x_ {3} lor x_ {4}) land ( neg x_ {2} lor x_ {3} lor neg x_ {4})}$.

Доказательство того, что QBF является PSPACE-полной проблемой, по сути является переформулировкой доказательства Теорема савича на языке логики и немного более технический.

Пазлы и игры

Проблема NP-complete в предыдущем разделе напоминает типичные головоломки: есть ли способ вставить значения, которые решают проблему? Соответственно проблема PSPACE-complete там напоминает игры: есть ли немного ход я могу сделать так, чтобы все ходов, которые может сделать мой противник, тогда будет немного ход, который я могу сделать, чтобы выиграть? В вопросе чередуются экзистенциальные и универсальные кванторы. Неудивительно, что многие головоломки оказываются NP-полными, а многие игры - PSPACE-полными.^[5]

Примеры игр, завершенных для PSPACE (когда обобщенный чтобы в них можно было играть на п × п доска) это игры Hex и Реверси пасьянс Час пик, Маджонг, Атомикс и Сокобан, а механический компьютер Кувырок Тьюринга. Некоторые другие обобщенные игры, такие как шахматы, шашки (проекты), и Идти находятся EXPTIME-завершено потому что игра между двумя идеальными игроками может быть очень долгой, поэтому они вряд ли будут в PSPACE. Но они станут PSPACE-завершено, если применяется полиномиальная оценка количества ходов.^[5]

Обратите внимание, что определение полноты PSPACE основано на асимптотический сложность: время, необходимое для решения проблемы размера п, в пределе как п растет неограниченно. Это означает конечный такие игры, как шашки (в которые играют на доске 8 × 8), никогда не могут быть завершены PSPACE, поскольку их можно решить в постоянном времени и пространстве, используя очень большой Справочная таблица (шашки уже решены таким образом). Вот почему все игры были изменены, играя в них на п × п доска вместо; в некоторых случаях, например, в шахматах, эти расширения являются искусственными.

Рекомендации

дальнейшее чтение

• Сипсер, Майкл (1997), «Раздел 8.3: Полнота PSPACE», Введение в теорию вычислений, PWS Publishing, стр.283–294, ISBN  0-534-94728-X.