PSPACE - PSPACE

Вопрос, Web Fundamentals.svgНерешенная проблема в информатике:
(больше нерешенных проблем в информатике)

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

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

Если обозначить через ПРОБЕЛ (т(п)), совокупность всех задач, которые могут быть решены Машины Тьюринга с помощью О(т(п)) место для некоторой функции т входного размера п, то мы можем определить PSPACE формально как[1]

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

Оказывается, позволяя машине Тьюринга быть недетерминированный не добавляет дополнительной мощности. Потому что Теорема савича,[2] NPSPACE эквивалентен PSPACE, по сути потому, что детерминированная машина Тьюринга может моделировать недетерминированная машина Тьюринга не занимая много места (даже если на это может потребоваться гораздо больше времени).[3] Так же дополняет все проблемы в PSPACE также находятся в PSPACE, что означает, что co-PSPACE = PSPACE.

Отношение среди других классов

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

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

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

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

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

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

Класс PSPACE закрыт на операции союз, дополнение, и Клини звезда.

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

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

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

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

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

PSPACE также равно PCTC, задачи, решаемые классическими компьютерами с использованием замкнутые времяподобные кривые,[6] а также в BQPCTC, проблемы решаемые квантовые компьютеры используя замкнутые времяподобные кривые.[7]

PSPACE-полнота

Основная статья: PSPACE-полный

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

Примером полной проблемы PSPACE является квантифицированная задача булевой формулы (обычно сокращенно QBF или же TQBF; то Т означает "истина").[8]

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

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