- Класс PSPACE
-
В теории сложности вычислений PSPACE - набор всех проблем разрешимости, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства.
Содержание
Машина Тьюринга с полиномиальным ограничением пространства
Если для данной машины Тьюринга верно, что существует полином p(n), такой что на любом входе размера n она посетит не более p(n) клеток, то такая машина называется машиной Тьюринга с полиномиальным ограничением пространства.
Можно показать, что:
1. Если машина Тьюринга с пространством, полиномиально ограниченным p(n), то существует константа c, при которой эта машина допускает свой вход длины n не более, чем за шагов.
Отсюда следует, что все языки машин Тьюринга с полиномиальным ограничением пространства — рекурсивные.
Классы PSPACE, NPSPACE
Класс языков PSPACE — множество языков, допустимых детерминированной машиной Тьюринга с полиномиальным ограничением пространства.
Класс языков NPSPACE — множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства.
Для классов языков PSPACE и NPSPACE верны следующие утверждения:
1. PSPACE = NPSPACE (этот факт доказывается теоремой Сэвича)
2. Контекстно-зависимые языки являются подмножеством PSPACE
3. :
4. :
5. Если язык принадлежит PSPACE, то существует машина Тьюринга с полиномиальным ограничением пространства, такая что она остановится за шагов для некоторого c и полинома p(n).
Известно, что хотя бы один из трех (Подмножество) символов в утверждении 3 должен быть строгим , но неизвестно какой. Есть предположение что все три .
PSPACE-полные языки
PSPACE-полный язык — язык , к которому сводятся по Карпу все PSPACE-языки за полиномиальное время.
Для PSPACE-полных языков известны следующие факты:
1.
2.
Пример 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»
Cчитаются лёгкими P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP Предпологаются сложными NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM Cчитаются сложными EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH Список алгоритмов Категория:- Классы сложности
Wikimedia Foundation. 2010.