Класс PSPACE

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

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

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

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

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

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

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

Классы PSPACE, NPSPACEПравить

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

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

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

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

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

3. $\text{NL}\subseteq <!--\; \subseteq \; -->\text{P}\subseteq <!--\; \subseteq \; -->\text{NP}\subseteq <!--\; \subseteq \; -->\text{PSPACE}\subseteq <!--\; \subseteq \; -->\text{EXPTIME}$${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$ 

4. $\text{NL}⊊<!--\; ⊊\; -->\text{PSPACE}⊊<!--\; ⊊\; -->\text{EXPSPACE}$${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$ 

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

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

PSPACE-полная задачаПравить

PSPACE-полная задача^[en] — это такая задача $\text{L}\in <!--\; \in \; -->\text{PSPACE},$${\mbox{L}}\in {\mbox{PSPACE}},$  к которой могут быть сведены по Карпу все проблемы класса PSPACE за полиномиальное время.

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

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

1.$\text{L}\in <!--\; \in \; -->\text{P}\Rightarrow <!--\; \Rightarrow \; -->\text{P}=\text{PSPACE};$${\mbox{L}}\in {\mbox{P}}\Rightarrow {\mbox{P}}={\mbox{PSPACE}};$ 

2.$\text{L}\in <!--\; \in \; -->\text{NP}\Rightarrow <!--\; \Rightarrow \; -->\text{NP}=\text{PSPACE}.$${\mbox{L}}\in {\mbox{NP}}\Rightarrow {\mbox{NP}}={\mbox{PSPACE}}.$ 

Пример PSPACE-полной задачи: нахождение истинных булевых формул с кванторами^[en].

ЛитератураПравить

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

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