Оглавление
PSPACE-полный
-
Определение PSPACE-полноты
- Задача считается PSPACE-полной, если она может быть решена с полиномиальным объемом памяти и может быть преобразована в любую другую задачу PSPACE за полиномиальное время.
- Задачи, которые являются PSPACE-полными, включают в себя определение свойств регулярных выражений, контекстно-зависимых грамматик, истинности булевых формул и другие.
-
Теория и редукции
- PSPACE-полнота определяется через многооднозначные и Тьюринговые редукции, которые преобразуют задачи одного типа в задачи другого типа.
- Неясно, приводят ли эти два типа редукций к различным классам задач PSPACE.
- Существует гипотеза Бермана-Хартманиса, утверждающая, что все PSPACE-полные множества выглядят одинаково и могут быть преобразованы друг в друга биекциями за полиномиальное время.
-
Примеры задач PSPACE-полноты
- Регулярные выражения, определяющие генерацию строк, являются PSPACE-полными.
- Проблема со словами для контекстно-зависимых грамматик является первой известной задачей PSPACE.
- Задачи реконфигурации, такие как проверка связности раскрасок графа, являются PSPACE-полными.
- Количественные булевые формулы и игры, такие как Hex и Reversi, являются примерами задач, которые могут быть интерпретированы как игры с выигрышной стратегией и являются PSPACE-полными.
-
PSPACE-полнота и размер входных данных
- Головоломки и игры с ограниченным количеством позиций не могут быть полностью заполнены, так как их можно решить за постоянное время и пространство.
- Для создания полноценных версий этих игр для PSPACE необходимо их расширить, чтобы количество позиций было неограниченным.
-
Рекомендации
- Для дальнейшего чтения предлагается ознакомиться с дополнительными материалами по теории сложности вычислений.
Полный текст статьи: