Решение задач с кванторами и игровых задач в полиномиальном пространстве - PSPACE: класс задач за пределами NP

В этом разделе мы поговорим о том, как все эти задачи решаются в полиномиальном пространстве. Как вы увидите, это будет сложнее (а в одном случае намного сложнее) той (простой) проблемы, с которой мы столкнулись при доказательстве принадлежности NP таких задач, как 3-SAT и задача о независимом множестве.

Начнем с задачи QSAT и задачи конкурентного размещения, а в следующем разделе будет рассмотрена задача построения плана.

Разработка алгоритма для QSAT

Сначала мы покажем, что задача QSAT может быть решена с полиномиальными затратами пространства. Как и в случае с 3-SAT, идея заключается в выполнении алгоритма “грубой силы”, обеспечивающего экономное использование пространства в процессе вычислений.

Базовое решение методом “грубой силы” выглядит так: чтобы разобраться с первым квантором ∃x₁, мы последовательно рассмотрим оба возможных значения x₁. Сначала мы назначаем x₁ = 0 и рекурсивно проверяем, дает ли оставшаяся часть формулы значение 1. Затем для значения x₁ = 1 проводится рекурсивная проверка того, дает ли оставшаяся часть формулы значение 1. Полная формула дает результат 1 в том, и только в том случае, если один из этих рекурсивных вызовов возвращает 1 — просто по определению квантора ∃.

По сути, это алгоритм “разделяй и властвуй”, который для входных данных с n переменными порождает два рекурсивных вызова с входными данными с n - 1 переменной каждый. Если сохранять всю работу, проделанную при рекурсивных вызовах, использование пространства S(n) будет удовлетворять рекуррентному отношению

S(n) ≤ 2S(n - 1) + p(n),

где p(n) — полиномиальная функция. Получается экспоненциальная граница, которая слишком велика.

К счастью, можно провести простую оптимизацию, которая значительно сократит затраты пространства. Разобравшись со случаем x₁ = 0, достаточно только сохранить один бит, представляющий результат рекурсивного вызова; всю остальную промежуточную работу можно отбросить. Таким образом, пространство, использованное при вычислениях для x₁ = 0, используется в вычислениях для x₁ = 1.

Ниже приведено компактное описание алгоритма.

Анализ алгоритма

Так как рекурсивные вызовы для х₁ = 0 и х₁ = 1 используют одно пространство, затраты пространства S(n) для задачи с n переменными просто полиномиальны по n плюс затраты пространства для одного рекурсивного вызова для задачи с n - 1 переменной.

S(n) ≤ S(n - 1) + p(n),

где p(n) — полиномиальная функция. Раскручивая это рекуррентное отношение, получаем

S(n) ≤ P(n) + p(n - 1) + p(n - 2) + ... + p(1) ≤ n ∙ p(n).

Так как p(n) — полиномиальная функция, то и n ∙ p(n) тоже, а следовательно, затраты пространства полиномиальны по n, как и требовалось:

Получаем следующий результат.

(9.4) Задача QSAT решается с полиномиальными затратами пространства.

Расширения: алгоритм для задачи конкурентного размещения

Для определения того, кто из игроков может обеспечить себе форсированный выигрыш в игре типа конкурентного размещения, можно воспользоваться очень похожим алгоритмом.

Предположим, игрок 1 ходит первым. Мы последовательно рассматриваем все возможные ходы. Для каждого из ходов мы проверяем, кто из игроков имеет форсированный выигрыш в полученной игре с первым ходом игрока 2. Если игрок 1 имеет форсированный выигрыш в какой-либо из этих игр, то он имеет форсированный выигрыш и в исходной позиции. Здесь, как и в случае алгоритма QSAT, важно то, что пространство может повторно использоваться при перемещении между кандидатами; достаточно хранить один бит, представляющий результат. В этом случае алгоритм потребляет полиномиальное пространство плюс пространство, необходимое для одного рекурсивного вывода в графе с меньшим количеством узлов. Как и в случае QSAT, мы получаем рекуррентное отношение

S(n) ≤ S(n - 1) + p(n),

для полиномиальной функции p(n).

В итоге получаем следующий результат:

(9.5) Задача конкурентного размещения решается с полиномиальными затратами пространства.