Класс PSPACE

Материал из Википедии — свободной энциклопедии

Содержание 1 Машина Тьюринга с полиномиальным ограничением пространства 2 Классы PSPACE, NPSPACE 3 PSPACE-полные языки 4 Литература

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

Если для данной машины Тьюринга верно, что существует полином 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. :

4. :

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

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

[править] PSPACE-полные языки

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

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

1.

2.

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

[править] Литература

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