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] $R$

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

Логика

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

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

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

Головоломки и игры

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

Также возможно, что головоломки, сыгранные одним игроком, будут PSPACE-полными. Их часто можно интерпретировать как проблемы переконфигурации, ^[10] и включают в себя игры-пасьянсы Rush Hour , Mahjong , Atomix и Sokoban , а также механический компьютер Turing Tumble . ^[11]

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

Ссылки

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

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

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