PSPACE
В сложности вычислений теории 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-полные задачи. См. PSPACE-complete для примеров проблем, которые предположительно связаны с PSPACE, но не с NP.
Свойства замыкания
[ редактировать ]Класс PSPACE закрыт по операциям объединения , дополнения и звезды Клини .
Другие характеристики
[ редактировать ]Альтернативная характеристика PSPACE — это набор задач, решаемых попеременной машиной Тьюринга за полиномиальное время, иногда называемый APTIME или просто AP. [4]
Логическая характеристика PSPACE из описательной теории сложности состоит в том, что это набор задач, выражаемых в логике второго порядка с добавлением оператора транзитивного замыкания . Полное транзитивное замыкание не требуется; достаточно коммутативного транзитивного замыкания и даже более слабых форм. Именно добавление этого оператора (возможно) отличает PSPACE от PH .
Главный результат теории сложности состоит в том, что PSPACE можно охарактеризовать как все языки, распознаваемые определенной интерактивной системой доказательства , определяющей класс IP . В этой системе есть всемогущая программа доказательства, пытающаяся убедить рандомизированную программу проверки за полиномиальное время в том, что строка присутствует в языке. Он должен иметь возможность убедить проверяющего с высокой вероятностью, если строка находится на языке, но не должен быть в состоянии убедить его, за исключением случаев с низкой вероятностью, если строка не находится на языке.
PSPACE можно охарактеризовать как класс квантовой сложности QIP . [5]
PSPACE также равен P CTC , проблемам, решаемым классическими компьютерами с использованием замкнутых времениподобных кривых . [6] а также BQP CTC — задачи, решаемые квантовыми компьютерами с использованием замкнутых времяподобных кривых. [7]
PSPACE-полнота
[ редактировать ]Язык B является PSPACE-полным, если он находится в PSPACE и является PSPACE-сложным, что означает, что для всех A ∈ PSPACE: , где означает, что существует полиномиальное сокращение числа «много-один» от A до B . PSPACE-полные задачи имеют большое значение для изучения задач PSPACE, поскольку они представляют собой самые сложные проблемы в PSPACE. Нахождение простого решения PSPACE-полной задачи означало бы, что у нас есть простое решение всех остальных проблем PSPACE, поскольку все проблемы PSPACE можно свести к PSPACE-полной задаче. [8]
Примером PSPACE-полной задачи является задача с количественной булевой формулой (обычно сокращенно QBF или TQBF ; T означает «истина»). [8]
Примечания
[ редактировать ]- ^ Арора и Барак (2009) стр.81
- ^ Арора и Барак (2009) стр.85
- ^ Арора и Барак (2009) стр.86
- ^ Арора и Барак (2009) стр.100
- ^ Рахул Джайн; Чжэнфэн Цзи; Сарвагья Упадхьяй; Джон Уотрус (июль 2009 г.). «QIP = PSPACE». arXiv : 0907.4737 [ квант-ph ].
- ^ С. Ааронсон (март 2005 г.). «NP-полные проблемы и физическая реальность». Новости СИГАКТ . arXiv : Quant-ph/0502072 . Бибкод : 2005quant.ph..2072A . дои : 10.1145/1052796.1052804 . S2CID 18759797 . .
- ^ Уотрус, Джон; Ааронсон, Скотт (2009). «Замкнутые времяподобные кривые делают квантовые и классические вычисления эквивалентными». Труды Королевского общества A: Математические, физические и технические науки . 465 (2102): 631. arXiv : 0808.2669 . Бибкод : 2009RSPSA.465..631A . дои : 10.1098/rspa.2008.0350 . S2CID 745646 .
- ^ Jump up to: а б Арора и Барак (2009) стр.83
Ссылки
[ редактировать ]- Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN 978-0-521-42426-4 . Збл 1193.68112 .
- Сипсер, Майкл (1997). Введение в теорию вычислений . Издательство ПВС. ISBN 0-534-94728-Х . Раздел 8.2–8.3 (Класс PSPACE, PSPACE-полнота), стр. 281–294.
- Пападимитриу, Христос (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 . Глава 19: Полиномиальное пространство, стр. 455–490.
- Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). Технология курса Томсона. ISBN 0-534-95097-3 . Глава 8: Космическая сложность
- Зоопарк сложности : PSPACE