Сложность вычислений
PSPACE и PSPACE-полнота
Шахматная программа проверяет все возможные ходы до конца партии. Для 8x8 доски - больше ходов, чем атомов во вселенной. P = NP? Никто не знает. Но мы знаем точно: шахматы в обобщённой n x n версии PSPACE-полны - их сложность характеризуется не временем, а памятью. TQBF (True Quantified Boolean Formula) - каноническая PSPACE-полная задача. Она лежит в основе формальной верификации программ, game solving, planning в AI. Понимание PSPACE объясняет, почему некоторые задачи сложны не потому, что занимают много времени - а потому что требуют экспоненциального пространства состояний.
- **Game AI**: обобщённые шахматы, го, Hex - PSPACE-полные. Пространство состояний экспоненциально.
- **Formal verification**: model checking верифицирует программы через PSPACE алгоритмы
- **Planning**: STRIPS planning (AI) - PSPACE-полная задача в общем случае
- **Logic synthesis**: оптимизация булевых схем через QBF solvers - практические PSPACE задачи
Теорема Савича и пространство памяти
В 1970 году Уолтер Савич доказал неожиданный результат: недетерминированное полиномиальное пространство (NPSPACE) = детерминированному полиномиальному пространству (PSPACE). Это контрастирует с P vs NP: для времени мы не знаем, равны ли P и NP. Для пространства - детерминизм и недетерминизм полиномиально эквивалентны. Теорема Савича имеет конструктивное доказательство через рекурсивный reachability алгоритм. В 1973 году Stockmeyer и Meyer доказали PSPACE-полноту TQBF. Это открыло целый класс задач - игры, планирование, верификацию - для точной характеристики сложности.
QBF: Quantified Boolean Formula
QBF расширяет SAT добавлением кванторов FORALL (для всех) и EXISTS (существует). SAT - частный случай QBF где все переменные экзистенциальны.
**Игровая интерпретация QBF:** EXISTS = ход MAX-игрока (пытается сделать формулу истинной). FORALL = ход MIN-игрока (пытается сделать формулу ложной). QBF истинна тогда и только тогда, когда у MAX-игрока есть выигрышная стратегия. Это прямая связь с PSPACE и game theory.
SAT: EXISTS x1...xn: phi. QBF: смешанные FORALL/EXISTS. Почему QBF предположительно сложнее SAT?
TQBF: PSPACE-полная задача
TQBF (True Quantified Boolean Formula) - задача определения истинности замкнутой QBF формулы. Это каноническая PSPACE-полная задача - аналог SAT для PSPACE.
**TQBF как PSPACE-complete:** Для доказательства PSPACE-полноты нужно показать: (1) TQBF in PSPACE - алгоритм выше, O(n) space. (2) Любая PSPACE задача полиномиально сводится к TQBF. Сведение использует конфигурации машины Тьюринга: состояния вычисления кодируются как булевы формулы с кванторами.
Рекурсивный алгоритм EVAL для QBF с n переменными использует O(n) пространства стека. Но перебирает 2^n комбинаций. Это соответствует PSPACE или EXPTIME?
PSPACE и теория игр
Двухместные игры с полной информацией и конечным числом ходов связаны с PSPACE: вопрос о наличии выигрышной стратегии - PSPACE-полная задача.
**Minimax и PSPACE:** Алгоритм minimax для игр - это реализация QBF вычисления. MAX слой = EXISTS квантор, MIN слой = FORALL квантор. Alpha-beta pruning сокращает дерево, но не меняет класс сложности задачи - PSPACE-полнота остаётся.
Шахматы на стандартной 8x8 доске решаются компьютером (таблицы эндшпилей до 7 фигур). Обобщённые шахматы на n x n доске - PSPACE-полны. Почему фиксированный размер упрощает задачу?
Теорема Савича: NPSPACE = PSPACE
Теорема Савича (1970): NPSPACE ⊆ DSPACE(f(n)^2). Следствие: PSPACE = NPSPACE. Для пространства недетерминизм не даёт экспоненциального ускорения - только квадратичный overhead.
**Почему NPSPACE = PSPACE, но P = NP неизвестно?** Ключевое различие: пространство можно переиспользовать (после использования ячейки памяти её можно освободить), а время - нет. Это даёт пространственным классам больше симметрии между детерминизмом и недетерминизмом.
PSPACE означает задачи с маленькими требованиями к памяти - меньше времени
PSPACE означает полиномиальное ПРОСТРАНСТВО, но время может быть экспоненциальным. PSPACE содержит задачи, которые сложнее NP.
За полиномиальное пространство s(n) машина Тьюринга может сделать до 2^s(n) шагов (разные конфигурации). PSPACE задачи могут требовать экспоненциального времени - поэтому PSPACE включает NP и предположительно строго больше.
Теорема Савича: NPSPACE ⊆ DSPACE(f(n)^2). Почему аналогичный результат NP ⊆ P так сложно доказать (или опровергнуть)?
Ключевые идеи
- **PSPACE**: задачи, решаемые детерминированной ТМ за полиномиальное ПРОСТРАНСТВО (но возможно экспоненциальное время)
- **PSPACE-полнота**: задача в PSPACE и любая PSPACE задача полиномиально сводится к ней. TQBF - канонический пример
- **Теорема Савича**: NPSPACE = PSPACE - для пространства недетерминизм не даёт экспоненциального ускорения
- **Иерархия**: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Все включения предположительно строгие, доказано только P != EXPTIME
- **TQBF**: QBF с чередующимися кванторами FORALL/EXISTS - полная задача для PSPACE
Вопросы для размышления
- Теорема Савича доказывает NPSPACE = PSPACE. Почему аналогичный результат для времени (NP = P) настолько сложнее доказать?
- PSPACE ⊆ EXPTIME - задачи с полиномиальным пространством требуют не более экспоненциального времени. Почему? Как количество конфигураций связано с пространством?
- TQBF с чередующимися кванторами - PSPACE-полная. Связана ли эта чередование с игровой интерпретацией (MAX/MIN игрок)?