Оглавление
ПРОСТРАНСТВО
-
Определение PSPACE
- PSPACE – это класс задач, решаемых машиной Тьюринга за полиномиальное время с использованием полиномиального пространства.
-
Эквивалентность NPSPACE и PSPACE
- NPSPACE эквивалентен PSPACE, так как детерминированная машина Тьюринга может имитировать недетерминированную с использованием дополнительного пространства.
-
Соотношение с другими классами сложности
- PSPACE строго меньше NL, P, NP, PH, EXPTIME и EXPSPACE.
- Неизвестно, какие из этих ограничений являются строгими.
-
Примеры задач в PSPACE
- Задачи, связанные с заполнением PSPACE, являются одними из самых сложных в этом классе.
- PSPACE-complete задачи представляют собой примеры проблем, которые предположительно связаны с PSPACE, но не с NP.
-
Закрытие класса PSPACE
- PSPACE закрыт относительно операций объединения, дополнения и звезды Клини.
-
Альтернативные характеристики PSPACE
- PSPACE может быть охарактеризован как набор задач, решаемых с помощью переменной машины Тьюринга за полиномиальное время.
- Логическая характеристика PSPACE основана на логике второго порядка с добавлением оператора транзитивного замыкания.
-
PSPACE и другие классы сложности
- PSPACE соответствует классу квантовой сложности QIP.
- PSPACE также соответствует PCTC и BQPCTC.
-
PSPACE-полнота
- Язык B является PSPACE-полным, если он находится в PSPACE и является PSPACE-жестким.
- Задачи с полным заполнением PSPACE имеют большое значение для изучения PSPACE, так как они представляют собой наиболее сложные задачи в этом классе.
-
Рекомендации по литературе
- Ссылки на разделы и главы в книгах, где можно найти дополнительную информацию о PSPACE.
Полный текст статьи: