Класс PSPACE

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

Машина Тьюринга с полиномиальным ограничением пространства

Если для данной машины Тьюринга верно, что существует полином p(n), такой что на любом входе размера n она посетит не более p(n) клеток, то такая машина называется машиной Тьюринга с полиномиальным ограничением пространства.

Можно показать, что:

1. Если машина Тьюринга с пространством, полиномиально ограниченным p(n), то существует константа c, при которой эта машина допускает свой вход длины n не более, чем за $c^{1+p(n)}$ шагов.

Отсюда следует, что все языки машин Тьюринга с полиномиальным ограничением пространства — рекурсивные.

Классы PSPACE, NPSPACE

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

Класс языков NPSPACE — множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства.

Для классов языков PSPACE и NPSPACE верны следующие утверждения:

1. PSPACE = NPSPACE (этот факт доказывается теоремой Сэвича)

2. Контекстно-зависимые языки являются подмножеством PSPACE

3. ${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$

4. ${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

5. Если язык принадлежит PSPACE, то существует машина Тьюринга с полиномиальным ограничением пространства, такая что она остановится за $c^{p(n)}$ шагов для некоторого c и полинома p(n).

Известно, что хотя бы один из трех $\subseteq$ (Подмножество) символов в утверждении ${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}$ должен быть строгим $\subsetneq$, но неизвестно какой. Так же хотя бы одно подмножество в утверждении ${\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$ должно быть строгим. Есть предположение что все эти включения строгие ($\subsetneq$).

PSPACE-полные языки

PSPACE-полный язык — язык $L\in PSPACE$, к которому сводятся по Карпу все PSPACE-языки за полиномиальное время.

Для PSPACE-полных языков известны следующие факты:

Если $L$ PSPACE-полный язык, то

1.$L\in P\Rightarrow P=PSPACE$

2.$L\in NP\Rightarrow NP=PSPACE$

Пример PSPACE-полного языка: язык истинных булевых формул с кванторами.

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.

• Hopcroft, Monwani, Ulman: «Introduction to Automata Theory, Languages, and Computation»