В теории сложности вычислений PSPACE — это набор всех задач решения , которые могут быть решены машиной Тьюринга с использованием полиномиального объема пространства .
Если мы обозначим SPACE( f ( n ) ), набор всех проблем, которые могут быть решены машинами Тьюринга с использованием пространства O ( f ( n )) для некоторой функции f входного размера n , тогда мы можем формально определить PSPACE как [1]
PSPACE — это строгое расширение набора контекстно-зависимых языков . [ нужна цитата ]
Оказывается, что недетерминированность машины Тьюринга не добавляет никакой дополнительной мощности. Из-за теоремы Савича [2] NPSPACE эквивалентен PSPACE, по существу потому, что детерминированная машина Тьюринга может моделировать недетерминированную машину Тьюринга , не требуя гораздо больше места (даже несмотря на то, что она может использовать гораздо больше времени ). [3] Кроме того, дополнения всех задач в PSPACE также находятся в PSPACE, а это означает, что co-PSPACE = PSPACE.
Между PSPACE и классами сложности NL , P , NP , PH , EXPTIME и EXPSPACE известны следующие отношения (обратите внимание, что ⊊, означающий строгое сдерживание, не то же самое, что ⊈):
Из третьей строки следует, что и в первой, и во второй строке хотя бы одно из заданных вложений должно быть строгим, но неизвестно какое. Широко распространено подозрение, что все они строгие.
Известно, что условия содержания в третьей линии являются строгими. Первое следует из прямой диагонализации ( теорема о пространственной иерархии , NL ⊊ NPSPACE) и того факта, что PSPACE = NPSPACE по теореме Савича . Второе следует просто из теоремы о пространственной иерархии.
Самыми сложными задачами в PSPACE являются PSPACE-полные задачи. См. 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]
