Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Нерешенная проблема в информатике :

(больше нерешенных проблем в информатике)

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

Формальное определение [ править ]

Если мы обозначим через SPACE ( t ( n )) множество всех проблем, которые могут быть решены машинами Тьюринга с использованием пространства O ( t ( n )) для некоторой функции t входного размера 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-complete. См. В PSPACE-complete примеры проблем, которые предположительно находятся в PSPACE, но не в NP.

Свойства закрытия [ править ]

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

Другие характеристики [ править ]

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

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

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

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

PSPACE также равна P КТК , задач , решаемых с помощью классических компьютеров с помощью кривых закрытой времениподобные , [6] , а также к BQP КТК , задач , решаемых квантовых компьютеров , использующих замкнутые кривые времениподобные. [7]

PSPACE-полнота [ править ]

Основная статья: PSPACE-complete

Язык B является PSPACE-полной , если она находится в PSPACE и это PSPACE твердолобый, что означает для всех A ∈ PSPACE, где означает , что существует полиномиальный многих один сокращение от A до B . PSPACE-полные задачи имеют большое значение для изучения проблем PSPACE, потому что они представляют собой самые сложные проблемы в PSPACE. Нахождение простого решения проблемы PSPACE-complete означало бы, что у нас есть простое решение для всех других проблем в PSPACE, потому что все проблемы PSPACE могут быть сведены к проблеме PSPACE-complete. [8]

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

Ссылки [ править ]

  1. ↑ Арора и Барак (2009), стр.81
  2. ↑ Арора и Барак (2009), стр.85
  3. ↑ Арора и Барак (2009), стр.86
  4. ^ Arora & Barak (2009) стр.100
  5. ^ Рахул Джайн; Чжэнфэн Цзи; Сарвагья Упадхьяй; Джон Уотроус (июль 2009 г.). «QIP = PSPACE». arXiv : 0907.4737 .
  6. ↑ С. Ааронсон (март 2005 г.). «NP-полные проблемы и физическая реальность». Новости SIGACT . arXiv : квант-ph / 0502072 . Bibcode : 2005quant.ph..2072A ..
  7. ^ Уотроус, Джон; Ааронсон, Скотт (2009). «Замкнутые времениподобные кривые делают квантовые и классические вычисления эквивалентными». Труды Королевского общества A: математические, физические и инженерные науки . 465 (2102): 631. arXiv : 0808.2669 . Bibcode : 2009RSPSA.465..631A . DOI : 10.1098 / rspa.2008.0350 .
  8. ^ а б Арора и Барак (2009) стр.83
  • Арора, Санджив ; Варак, Вооз (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