В теории сложности вычислений PSPACE — это набор всех задач принятия решений , которые могут быть решены машиной Тьюринга с использованием полиномиального объема памяти .
Если обозначить через SPACE( f ( n )) множество всех задач, которые могут быть решены машинами Тьюринга с использованием пространства O ( f ( n )) для некоторой функции f входного размера n , то мы можем формально определить PSPACE как [1]
Оказывается, что разрешение машине Тьюринга быть недетерминированной не добавляет никакой дополнительной мощности. Из-за теоремы Сэвича [2] NPSPACE эквивалентна PSPACE, по сути, потому что детерминированная машина Тьюринга может имитировать недетерминированную машину Тьюринга, не нуждаясь в большем количестве памяти (хотя она может использовать гораздо больше времени ). [3] Кроме того, дополнения всех задач в PSPACE также находятся в PSPACE, что означает, что co-PSPACE = PSPACE. [ необходима цитата ]
Известны следующие соотношения между PSPACE и классами сложности NL , P , NP , PH , EXPTIME и EXPSPACE (обратите внимание, что ⊊ обозначает строгое включение, не путать с ⊈):
Из третьей строки следует, что и в первой, и во второй строке по крайней мере одно из множеств включений должно быть строгим, но неизвестно, какое именно. Широко распространено подозрение, что все они строгие.
Известно, что оба включения в третьей строке являются строгими. Первое следует из прямой диагонализации ( теорема об иерархии пространства , NL ⊊ NPSPACE) и того факта, что PSPACE = NPSPACE по теореме Сэвича . Второе следует просто из теоремы об иерархии пространства.
Самые сложные проблемы в PSPACE — это проблемы PSPACE-complete. См. PSPACE-complete для примеров проблем, которые предположительно находятся в PSPACE, но не в NP.
Класс PSPACE закрыт относительно операций объединения , дополнения и звезды Клини .
Альтернативной характеристикой PSPACE является набор задач, разрешимых с помощью альтернативной машины Тьюринга за полиномиальное время, иногда называемое APTIME или просто AP. [4]
Логическая характеристика PSPACE из теории дескриптивной сложности заключается в том, что это набор проблем, выражаемых в логике второго порядка с добавлением оператора транзитивного замыкания . Полное транзитивное замыкание не требуется; достаточно коммутативного транзитивного замыкания и даже более слабых форм. Именно добавление этого оператора (возможно) отличает PSPACE от PH .
Главным результатом теории сложности является то, что PSPACE можно охарактеризовать как все языки, распознаваемые определенной интерактивной системой доказательств , той, которая определяет класс IP . В этой системе есть всемогущий доказывающий, пытающийся убедить рандомизированного полиномиального времени верификатора, что строка находится в языке. Он должен быть в состоянии убедить верификатора с высокой вероятностью, если строка находится в языке, но не должен быть в состоянии убедить его, за исключением случаев с низкой вероятностью, если строка не находится в языке.
PSPACE можно охарактеризовать как квантовый класс сложности QIP . [5]
PSPACE также равен P CTC , задачам, решаемым классическими компьютерами с использованием замкнутых времениподобных кривых , [6] а также BQP CTC , задачам, решаемым квантовыми компьютерами с использованием замкнутых времениподобных кривых. [7]
Язык B является PSPACE-полным, если он находится в PSPACE и является PSPACE-трудным, что означает для всех A ∈ PSPACE, , где означает, что существует полиномиальное время многоединичного сведения от A к B . PSPACE-полные задачи имеют большое значение для изучения задач PSPACE, поскольку они представляют собой самые сложные задачи в PSPACE. Нахождение простого решения для PSPACE-полной задачи будет означать, что у нас есть простое решение для всех других задач в PSPACE, поскольку все задачи PSPACE могут быть сведены к PSPACE-полной задаче. [8]
Примером PSPACE-полной задачи является задача с квантифицированной булевой формулой (обычно сокращенно QBF или TQBF ; T означает «истина»). [8]
