PSPACE-полный

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

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

Теория

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

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

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

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

Примеры

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

Учитывая регулярное выражение , определение того, генерирует ли оно каждую строку в своем алфавите, является PSPACE-полным. ^[6] ${\displaystyle R}$

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

Логика

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

$${\displaystyle \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}).}$$

^[1]

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

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

Пазлы и игры

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

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

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

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

1. Гари, Майкл Р .; Джонсон, Дэвид С. (1979), «Раздел 7.4: Полнота полиномиального пространства», Компьютеры и трудноразрешимость: Руководство по теории NP-полноты , WH Freeman, стр. 170–177, ISBN 0-7167-1045-5
2. Арора, Санджив; Барак, Боаз (2009), Сложность вычислений: современный подход, Cambridge University Press, стр. 92, ISBN 978-1-139-47736-9
3. Ватанабэ, Осаму; Тан, Шоу Вэнь (1992), «О полиномиальном времени Тьюринга и многоединственной полноте в PSPACE», Theoretical Computer Science , 97 (2): 199–215, doi : 10.1016/0304-3975(92)90074-P , МР  1163815
4. Хичкок, Джон М.; Паван, Адури (2013), «Сокращения, увеличивающие длину для PSPACE-полноты», в Чаттерджи, Кришненду; Сгалл, Ири (ред.), Математические основы информатики 2013 – 38-й Международный симпозиум, MFCS 2013, Клостернойбург, Австрия, 26–30 августа 2013 г., Труды , Конспекты лекций по информатике, том. 8087, Springer, стр. 540–550, номер документа : 10.1007/978-3-642-40313-2_48, MR  3126236.
5. Берман, Л.; Хартманис, Дж. (1977), «Об изоморфизмах и плотности NP и других полных наборов», SIAM Journal on Computing , 6 (2): 305–322, doi : 10.1137/0206023, hdl : 1813/7101 , MR  0455536
6. Хант, Гарри Б. III (1973), «О временной и ленточной сложности языков, I», в Ахо, Альфред В.; Бородин, Аллан; Констебль, Роберт Л.; Флойд, Роберт В.; Харрисон, Майкл А.; Карп, Ричард М.; Стронг, Х. Рэймонд (ред.), Труды 5-го ежегодного симпозиума ACM по теории вычислений, 30 апреля - 2 мая 1973 г., Остин, Техас, США, Ассоциация вычислительной техники, стр. 10–19, doi : 10.1145. /800125.804030 , hdl : 1813/6007 , S2CID  15937339, заархивировано из оригинала 17 января 2024 г.
7. Курода, С.-Ю. (1964), «Классы языков и линейно ограниченных автоматов», Информация и вычисления , 7 (2): 207–223, doi : 10.1016/s0019-9958(64)90120-2 , MR  0169724
8. Бонсма, Пол; Сереседа, Луис (2009), «Нахождение путей между раскрасками графов: PSPACE-полнота и суперполиномиальные расстояния», Theoretical Computer Science , 410 (50): 5215–5226, doi : 10.1016/j.tcs.2009.08.023 , MR  2573973
9. Джонсон, Мэтью; Крач, Дитер; Крач, Стефан; Патель, Виреш; Паулусма, Даниэль (2016), «Нахождение кратчайших путей между раскрасками графа» (PDF) , Algorithmica , 75 (2): 295–321, doi : 10.1007/s00453-015-0009-7, MR  3506195, S2CID  6810123
10. Хирн, Роберт А.; Демейн, Эрик Д. (2009), Игры, головоломки и вычисления , А.К. Петерс
11. Эппштейн, Дэвид , Вычислительная сложность игр и головоломок

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

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