Класс PSPACE

Иерархия классов сложности.

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

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

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

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

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

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

Классы PSPACE, NPSPACE

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

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

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

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

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

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

4. $\text{NL}⊊\text{PSPACE}⊊\text{EXPSPACE}$

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

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

PSPACE-полная задача

Шаблон:Нп5 — это такая задача $\text{L}\in \text{PSPACE},$ к которой могут быть сведены по Карпу все проблемы класса PSPACE за полиномиальное время.

Про PSPACE-полную задачу известны следующие факты:

Если $\text{L}$ является PSPACE-полной задачей, то

1.$\text{L}\in \text{P}\Rightarrow \text{P}=\text{PSPACE};$

2.$\text{L}\in \text{NP}\Rightarrow \text{NP}=\text{PSPACE}.$

Пример PSPACE-полной задачи: Шаблон:Iw.

Литература

• Шаблон:Книга

• Hopcroft, Motwani, Ullman: «Introduction to Automata Theory, Languages, and Computation»

Шаблон:Классы сложности