Класс сложности PSPACE — набор всех проблем разрешимости в теории сложности вычислений, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства.
Машина Тьюринга с полиномиальным ограничением пространства Если для данной машины Тьюринга верно, что существует полином , такой что на любом входе размера она посетит не более клеток, то такая машина называется машиной Тьюринга с полиномиальным ограничением пространства.
Можно показать, что:
1. Если машина Тьюринга с пространством, полиномиально ограниченным , то существует константа , при которой эта машина допускает свой вход длины не более, чем за шагов.
Отсюда следует, что все языки машин Тьюринга с полиномиальным ограничением пространства — рекурсивные.
Классы PSPACE, NPSPACE Класс языков PSPACE — множество языков, допустимых детерминированной машиной Тьюринга с полиномиальным ограничением пространства.
Класс языков NPSPACE — множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства.
Для классов языков PSPACE и NPSPACE верны следующие утверждения:
1. PSPACE = NPSPACE (этот факт доказывается теоремой Сэвича)
2. Контекстно-зависимые языки являются подмножеством PSPACE
3.
4.
5. Если язык принадлежит PSPACE, то существует машина Тьюринга с полиномиальным ограничением пространства, такая что она остановится за шагов для некоторого и полинома .
Известно, что хотя бы один из трёх символов включения в утверждении должен быть строгим (то есть исключать равенство множеств, отношение между которыми он описывает), но неизвестно, который из них. Также хотя бы одно подмножество в утверждении должно быть собственным (то есть хотя бы один символ включения должен быть строгим). Есть предположение, что все эти включения строгие .
PSPACE-полная задача — это такая задача к которой могут быть сведены по Карпу все проблемы класса PSPACE за полиномиальное время.
Про PSPACE-полную задачу известны следующие факты:
Если является PSPACE-полной задачей, то
1.
2.
Пример PSPACE-полной задачи: .
Литература
Hopcroft, Motwani, Ullman: «Introduction to Automata Theory, Languages, and Computation»
Категория:Классы сложности