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

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

Многие подозревают, что PSPACE-полные проблемы лежат за пределами более известных классов сложности P и NP , но это не известно. [1] Известно, что они лежат за пределами класса NC (класс задач с высокоэффективными параллельными алгоритмами ), потому что задачи в NC могут быть решены в объеме пространства, полиномиальном от логарифма размера входных данных, а класс проблем, решаемых в таком небольшом пространстве, строго содержится в PSPACE по теореме пространственной иерархии .

Примеры [ править ]

Основная статья: Список проблем PSPACE-complete

Регулярные выражения и автоматы [ править ]

Учитывая регулярное выражение R , определение того, генерирует ли оно каждую строку по своему алфавиту, является PSPACE-полным. [2]

Связанный результат состоит в том, что класс языков, распознаваемых с нулевой ошибкой автоматами с двусторонней бесконечной случайной лентой, равен недетерминированному линейному пространству . Это справедливо как для двустороннего, так и для многопроходного одностороннего доступа к входу. Проверка того, принимает ли автомат (с двусторонней бесконечной случайной лентой) слово с нулевой ошибкой, завершается NSPACE (O (kn)), где n - размер ввода, а k - количество состояний.

Контекстно-зависимые грамматики [ править ]

Первой известной неполной проблемой PSPACE была проблема со словом для детерминированных контекстно-зависимых грамматик . В проблеме слов для контекстно-зависимых грамматик каждому дается набор грамматических преобразований, которые могут увеличивать, но не могут уменьшаться, длину предложения, и он хочет определить, может ли данное предложение быть произведено этими преобразованиями. Техническое условие «детерминизма» (подразумевающее примерно то, что каждое преобразование делает очевидным, что оно было использовано) гарантирует, что этот процесс может быть решен в полиномиальном пространстве, и Курода (1964) показал, что каждая (возможно недетерминированная) программа, вычисляемая в линейном Космосможет быть преобразован в синтаксический анализ контекстно-зависимой грамматики таким образом, чтобы сохранить детерминизм. [3] В 1970 году теорема Сэвича показала, что PSPACE закрывается при недетерминировании, подразумевая, что даже недетерминированные контекстно-зависимые грамматики находятся в PSPACE.

Количественные логические формулы [ править ]

В настоящее время архетипическая проблема PSPACE-complete обычно рассматривается как проблема количественной булевой формулы (обычно сокращенно QBF или TQBF; T означает «истина»), обобщение первой известной NP-полной проблемы, проблемы булевой выполнимости. (СИДЕЛ). Проблема выполнимости - это проблема того, есть ли присвоения значений истинности переменным, которые делают логическое выражение истинным. [4] Например, одним из примеров SAT может быть вопрос о том, верно ли следующее:

Проблема количественной булевой формулы отличается тем, что допускает как универсальную, так и экзистенциальную количественную оценку значений переменных:

.

Доказательство того, что QBF является PSPACE-полной проблемой, по сути является переформулировкой доказательства теоремы Сэвича на языке логики и носит более технический характер.

Пазлы и игры [ править ]

Список игр по полноте для PSPACE или других классов сложности см. В разделе « Сложность игры» .

Проблема NP-complete в предыдущем разделе напоминает типичные головоломки: есть ли способ вставить значения, которые решают проблему? Соответственно, проблема PSPACE-complete напоминает игры: есть ли какой-нибудь ход, который я могу сделать, так что для всех ходов, которые может сделать мой противник, будет какой-то ход, который я могу сделать, чтобы выиграть? В вопросе чередуются экзистенциальные и универсальные кванторы. Неудивительно, что многие головоломки оказываются NP-полными, а многие игры - PSPACE-полными. [5]

Примерами игр, которые являются PSPACE-полными (если обобщить их так, чтобы в них можно было играть на доске n × n ), являются игры Hex и Reversi, пасьянсы Rush Hour , Mahjong , Atomix и Sokoban , а также механический компьютер Turing Tumble . Некоторые другие обобщенные игры, такие как шахматы , шашки (шашки) и го , завершаются EXPTIME, потому что игра между двумя идеальными игроками может быть очень долгой, поэтому они вряд ли будут в PSPACE. Но они станутPSPACE -завершено, если принудительно установлена ​​полиномиальная оценка количества ходов. [5]

Обратите внимание, что определение PSPACE-полноты основано на асимптотической сложности: время, необходимое для решения задачи размера n , в пределе, когда n неограниченно растет. Это означает, что такая конечная игра, как шашки (в которую играют на доске 8 × 8), никогда не может быть PSPACE-полной, поскольку они могут быть решены в постоянном времени и пространстве с использованием очень большой таблицы поиска (шашки уже решены таким образом) . Вот почему все игры были изменены, вместо этого играя их на доске n × n ; в некоторых случаях, например, в шахматах, эти расширения являются искусственными.

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

  1. ^ Арора, Санджив; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, стр. 92, ISBN 9781139477369
  2. ^ Хант, HB, III (1973), «О времени и сложности ленты языков. I», Пятый ежегодный симпозиум ACM по теории вычислений (Остин, Техас, 1973) , доц. Comput. Mach., New York, pp. 10–19, MR 0421145. 
  3. ↑ Курода, С.-Й. (1964), "Классы языков и линейно-ограниченных автоматов", информации и вычислений , 7 : 207-223, DOI : 10.1016 / s0019-9958 (64) 90120-2 , МР 0169724 
  4. ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), "Раздел 7.4: Полнота полиномиального пространства", Компьютеры и неразрешимость: Руководство по теории NP- полноты , WH Freeman, стр.  170–177 , ISBN 0-7167-1045-5
  5. ^ а б Эппштейн, Дэвид , Вычислительная сложность игр и головоломок

Дальнейшее чтение [ править ]

  • Сипсер, Майкл (1997), «Раздел 8.3: Полнота PSPACE», Введение в теорию вычислений , PWS Publishing, стр.  283–294 , ISBN 0-534-94728-X.