Введение

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

Теория

Проблема определяется как PSPACE-полная, если она может быть решена, используя полиномиальное количество памяти (то есть принадлежит классу PSPACE), и любая задача из PSPACE может быть сведена за полиномиальное время к эквивалентному экземпляру данной задачи. Широко распространено предположение, что PSPACE-полные задачи находятся вне более известных классов сложности P (полиномиальное время) и NP (недетерминированное полиномиальное время), но это не доказано. Известно, что они не принадлежат классу NC, классу задач, для которых существуют высокоэффективные параллельные алгоритмы, поскольку задачи из NC могут быть решены, используя количество памяти, полиномиальное относительно логарифма размера входных данных, а класс задач, разрешимых с использованием столь малого объема памяти, строго содержится в PSPACE согласно теореме об иерархии сложности по памяти. Обычно при определении PSPACE-полноты рассматриваются полиномиальные сводения «многие к одному», то есть преобразования, которые переводят один экземпляр задачи одного типа в эквивалентный один экземпляр задачи другого типа. Однако полноту можно определить и с помощью сводений Тьюринга, в которых одна задача решается за полиномиальное количество вызовов подпрограммы для другой задачи. Неизвестно, приводят ли эти два типа сводений к различным классам PSPACE-полных задач. Также рассматривались и другие типы сводений, например, сводения «многие к одному», которые всегда увеличивают длину преобразованного входного экземпляра. Версия гипотезы Бермана — Хартманиса для PSPACE-полных множеств утверждает, что все такие множества эквивалентны, в том смысле, что все они могут быть преобразованы друг в друга биекциями за полиномиальное время.

Официальные языки

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

Логика

Стандартная задача, полная по классу PSPACE и используемая во многих других доказательствах полноты PSPACE, — это задача о квантованной булевой формуле, являющаяся обобщением задачи выполнимости булевых формул (SAT). На вход задаче о квантованной булевой формуле подаётся булева формула, все переменные которой квантифицированы универсально или экзистенциально, например:

Результатом работы задачи является значение квантованной формулы. Определение этого значения является задачей, полной по классу PSPACE.

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

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