Класс PSPACE

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

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

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

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

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

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

Классы PSPACE, NPSPACE

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

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

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

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

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

3. :<math>\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}</math>

4. :<math>\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}</math>

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

Известно, что хотя бы один из трех <math>\subseteq</math> (Подмножество) символов в утверждении 3 должен быть строгим <math>\subsetneq</math>, но неизвестно какой. Есть предположение что все три <math>\subsetneq</math>.

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

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

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

<math>L\in PSPACEC \Rightarrow </math>

1.<math>L\in P \Rightarrow P = PSPACE</math>

2.<math>L\in NP \Rightarrow NP = PSPACE </math>

Пример 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»

Отрывок, характеризующий Класс PSPACE

– Дронушка, Алпатыч куда то уехал, мне не к кому обратиться. Правду ли мне говорят, что мне и уехать нельзя?
– Отчего же тебе не ехать, ваше сиятельство, ехать можно, – сказал Дрон.
– Мне сказали, что опасно от неприятеля. Голубчик, я ничего не могу, ничего не понимаю, со мной никого нет. Я непременно хочу ехать ночью или завтра рано утром. – Дрон молчал. Он исподлобья взглянул на княжну Марью.
– Лошадей нет, – сказал он, – я и Яков Алпатычу говорил.
– Отчего же нет? – сказала княжна.
– Все от божьего наказания, – сказал Дрон. – Какие лошади были, под войска разобрали, а какие подохли, нынче год какой. Не то лошадей кормить, а как бы самим с голоду не помереть! И так по три дня не емши сидят. Нет ничего, разорили вконец.
Княжна Марья внимательно слушала то, что он говорил ей.
– Мужики разорены? У них хлеба нет? – спросила она.
– Голодной смертью помирают, – сказал Дрон, – не то что подводы…
– Да отчего же ты не сказал, Дронушка? Разве нельзя помочь? Я все сделаю, что могу… – Княжне Марье странно было думать, что теперь, в такую минуту, когда такое горе наполняло ее душу, могли быть люди богатые и бедные и что могли богатые не помочь бедным. Она смутно знала и слышала, что бывает господский хлеб и что его дают мужикам. Она знала тоже, что ни брат, ни отец ее не отказали бы в нужде мужикам; она только боялась ошибиться как нибудь в словах насчет этой раздачи мужикам хлеба, которым она хотела распорядиться. Она была рада тому, что ей представился предлог заботы, такой, для которой ей не совестно забыть свое горе. Она стала расспрашивать Дронушку подробности о нуждах мужиков и о том, что есть господского в Богучарове.
– Ведь у нас есть хлеб господский, братнин? – спросила она.
– Господский хлеб весь цел, – с гордостью сказал Дрон, – наш князь не приказывал продавать.
– Выдай его мужикам, выдай все, что им нужно: я тебе именем брата разрешаю, – сказала княжна Марья.
Дрон ничего не ответил и глубоко вздохнул.
– Ты раздай им этот хлеб, ежели его довольно будет для них. Все раздай. Я тебе приказываю именем брата, и скажи им: что, что наше, то и ихнее. Мы ничего не пожалеем для них. Так ты скажи.
Дрон пристально смотрел на княжну, в то время как она говорила.
– Уволь ты меня, матушка, ради бога, вели от меня ключи принять, – сказал он. – Служил двадцать три года, худого не делал; уволь, ради бога.
Княжна Марья не понимала, чего он хотел от нее и от чего он просил уволить себя. Она отвечала ему, что она никогда не сомневалась в его преданности и что она все готова сделать для него и для мужиков.