PSPACE-полный

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

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

Теория

Задача считается PSPACE-полной, если ее можно решить, используя полиномиальный объем памяти (она принадлежит PSPACE), и каждая задача в PSPACE может быть преобразована за полиномиальное время в эквивалентный экземпляр данной задачи.

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

Преобразования, которые обычно рассматриваются при определении PSPACE-полноты, представляют собой редукции «многие-единицы» за полиномиальное время , преобразования, которые преобразуют один экземпляр проблемы одного типа в эквивалентный единственный экземпляр проблемы другого типа. Однако полноту также можно определить с помощью сокращений Тьюринга , при которых одна проблема может быть решена за полиномиальное количество вызовов подпрограммы для другой задачи. Неизвестно, приводят ли эти два типа редукций к разным классам PSPACE-полных задач. Также рассматривались другие типы сокращений, такие как сокращения «многие единицы», которые всегда увеличивают длину преобразованного входного сигнала.

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

Примеры

Основная статья: Список проблем, полных PSPACE

Формальные языки

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

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

Логика

Стандартная проблема PSPACE-полноты, используемая во многих других результатах PSPACE-полноты, представляет собой проблему количественной булевой формулы , обобщение проблемы булевой выполнимости . Задача количественной булевой формулы принимает в качестве входных данных логическое выражение, все его переменные которого количественно определены либо универсально, либо экзистенциально, например: $$\exists 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}).$$ Результатом задачи является значение количественного выражения. Поиск этого значения является PSPACE-полным.

Реконфигурация

Проблемы реконфигурации касаются связности пространства состояний решений комбинаторной задачи. Например, проверка того, могут ли две 4-раскраски графа быть соединены друг с другом ходами, которые меняют цвет одной вершины за раз, сохраняя на каждом этапе допустимую 4-раскраску, является PSPACE-полной. хотя ту же задачу для 3-раскрасок можно решить за полиномиальное время. Другое семейство задач реконфигурации, используемое аналогично количественным булевым формулам в качестве основы для доказательства PSPACE-полноты многих других проблем в этой области, включает в себя недетерминированную логику ограничений , в которой состояния представляют собой ориентации графа ограничений, на которые распространяются определенные ограничения на количество ребра должны быть ориентированы внутрь в каждой вершине, и при этом переходы от состояния к состоянию меняют ориентацию одного ребра на противоположную.

Пазлы и игры

Список игр по полноте для PSPACE или других классов сложности см. в разделе Сложность игры .

Задачу с количественной булевой формулой можно интерпретировать как игру двух игроков: проверяющего и фальсификатора. Игроки делают ходы, которые заполняют значения квантифицированных переменных в том порядке, в котором они вложены: верификатор заполняет экзистенциально квантифицированные переменные, а фальсификатор заполняет универсально квантифицированные переменные; игру выигрывает проверяющий, если заполненная формула становится истинной, и фальсифицирующий в противном случае. Количественная формула верна тогда и только тогда, когда проверяющий имеет выигрышную стратегию. Аналогичным образом, проблема определения победителя или проигравшего во многих других комбинаторных играх оказывается PSPACE-полной. Примеры игр, которые являются PSPACE-полными (если они обобщены так, что в них можно играть на $n\times n$ доска) — это игры Hex и Reversi . Некоторые другие обобщенные игры, такие как шахматы , шашки (шашки) и го , являются EXPTIME-полными , поскольку игра между двумя идеальными игроками может быть очень продолжительной, поэтому они вряд ли будут находиться в PSPACE. Но они станут PSPACE-полными, если будет соблюдаться полиномиальная граница количества ходов.

Головоломки, в которые играет один игрок, также могут быть PSPACE-полными. Их часто можно интерпретировать как проблемы реконфигурации. и включают в себя пасьянсы «Час пик» , «Маджонг» , «Атомикс» и «Сокобан» , а также механический компьютер «Тьюринг Тамбл» .

PSPACE-полнота основана на сложности как функции размера входных данных. $n$, в пределе как $n$ растет без ограничений. Головоломки или игры с ограниченным количеством позиций, например, шахматы на обычной $8\times 8$ доска не может быть PSPACE-полной, поскольку их можно решить за постоянное время и пространство, используя очень большую справочную таблицу . Чтобы сформулировать PSPACE-полные версии этих игр, их необходимо модифицировать таким образом, чтобы число их позиций было неограниченным, например, играя в них на $n\times n$ вместо этого доска. В некоторых случаях, например в шахматах, эти расширения являются искусственными.

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

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