PSPACE - PSPACE

В теории сложности вычислений , PSPACE это совокупность всех задач принятия решений , которые могут быть решены с помощью машины Тьюринга , используя полиномиальное количество пространства .

Формальное определение

Если мы обозначим через SPACE ( t ( n )) множество всех проблем, которые могут быть решены машинами Тьюринга с использованием пространства O ( t ( n )) для некоторой функции t входного размера n , то мы можем определить PSPACE формально как

${\ displaystyle {\ mathsf {PSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mathsf {SPACE}} (n ^ {k}).}$

PSPACE - это строгий надмножество набора контекстно-зависимых языков .

Оказывается, позволяя машине Тьюринга быть недетерминирован не добавляет дополнительную мощность. Благодаря теореме Сэвича, NPSPACE эквивалентен PSPACE, по сути потому, что детерминированная машина Тьюринга может моделировать недетерминированную машину Тьюринга, не занимая гораздо больше места (даже если она может использовать гораздо больше времени). Кроме того , комплементы всех проблем в PSPACE также в PSPACE, а это означает , что со-PSPACE = PSPACE.

Связь между другими классами

Представление отношения между классами сложности

Известны следующие отношения между PSPACE и классами сложности NL , P , NP , PH , EXPTIME и EXPSPACE (обратите внимание, что ⊊, означающее строгое включение, не то же самое, что ⊈):

${\ displaystyle {\ begin {array} {l} {\ mathsf {NL \ substeq P \ substeq NP \ substeq PH \ substeq PSPACE}} \\ {\ mathsf {PSPACE \ substeq EXPTIME \ substeq EXPSPACE}} \\ {\ mathsf {NL \ subsetneq PSPACE \ subsetneq EXPSPACE}} \\ {\ mathsf {P \ subsetneq EXPTIME}} \ end {array}}}$

Из третьей строки следует, что как в первой, так и во второй строке, по крайней мере, одно из установленных ограничений должно быть строгим, но неизвестно, какое именно. Многие подозревают, что все они строгие.

Известно, что условия содержания в третьей линии очень строгие. Первое следует из прямой диагонализации ( теорема пространственной иерархии , NL ⊊ NPSPACE) и того факта, что PSPACE = NPSPACE через теорему Савича . Второе просто следует из теоремы о пространственной иерархии.

Самые сложные проблемы в PSPACE - это проблемы PSPACE-complete. См. В PSPACE-complete примеры проблем, которые предположительно находятся в PSPACE, но не в NP.

Свойства закрытия

Класс PSPACE замкнут относительно объединения операций , дополнения и звезды Клини .

Другие характеристики

Альтернативная характеристика PSPACE - это набор проблем, решаемых альтернативной машиной Тьюринга за полиномиальное время, иногда называемой APTIME или просто AP.

Логическая характеристика PSPACE из описательной теории сложности состоит в том, что это набор проблем, которые можно выразить в логике второго порядка с добавлением оператора транзитивного замыкания . Полное переходное замыкание не требуется; достаточно коммутативного транзитивного замыкания и даже более слабых форм. Добавление этого оператора (возможно) отличает PSPACE от PH .

Главный результат теории сложности состоит в том, что PSPACE можно охарактеризовать как все языки, распознаваемые конкретной интерактивной системой доказательства , определяющей класс IP . В этой системе есть всемогущий доказывающий, пытающийся убедить рандомизированный верификатор с полиномиальным временем, что строка находится на языке. Он должен быть в состоянии убедить проверяющего с высокой вероятностью, если строка находится на языке, но не должен быть в состоянии убедить его, кроме как с низкой вероятностью, если строка не на языке.

PSPACE можно охарактеризовать как квантовый класс сложности QIP .

PSPACE также равен P _CTC , задачам, решаемым классическими компьютерами с использованием замкнутых времениподобных кривых , а также BQP _CTC , задачам, решаемым квантовыми компьютерами с использованием замкнутых времениподобных кривых.

PSPACE-полнота

Язык B является PSPACE-полной , если она находится в PSPACE и это PSPACE твердолобый, что означает для всех A ∈ PSPACE, где означает , что существует полиномиальный многих один сокращение от A до B . PSPACE-полные задачи имеют большое значение для изучения проблем PSPACE, потому что они представляют собой самые сложные проблемы в PSPACE. Нахождение простого решения проблемы PSPACE-complete означало бы, что у нас есть простое решение для всех других проблем в PSPACE, потому что все проблемы PSPACE могут быть сведены к проблеме PSPACE-complete. ${\ displaystyle A \ leq _ {\ text {P}} B}$${\ displaystyle A \ leq _ {\ text {P}} B}$

Примером проблемы PSPACE-complete является проблема количественной логической формулы (обычно сокращенно QBF или TQBF ; T означает «истина»).

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

• Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN 978-0-521-42426-4. Zbl  1193.68112 .
• Сипсер, Майкл (1997). Введение в теорию вычислений . PWS Publishing. ISBN 0-534-94728-X. Раздел 8.2–8.3 (Класс PSPACE, полнота PSPACE), стр. 281–294.
• Пападимитриу, Христос (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1. Глава 19: Полиномиальное пространство, стр. 455–490.
• Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). Thomson Course Technology. ISBN 0-534-95097-3. Глава 8: Сложность космоса
• Зоопарк сложности : PSPACE