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