PSPACE

Мы будем изучать класс PSPACE — множество всех задач, которые могут быть решены алгоритмом с полиномиальной пространственной сложностью (то есть алгоритмом с затратами пространства, полиномиальными по размерам входных данных).

Для начала рассмотрим отношение PSPACE к классам задач, которые рассматривались выше. Прежде всего, за полиномиальное время алгоритм может потреблять не более чем полиномиальное пространство; итак, можно утверждать:

(9.1) P Ӭ PSPACE

Однако множество PSPACE намного шире. Например, рассмотрим алгоритм, который просто считает от 0 до 2n – 1 в двоичной системе. Он просто реализует n-разрядный счетчик, который работает по тому же принципу, что и одометр в автомобиле. Таким образом, алгоритм выполняется за экспоненциальное время, после чего останавливается; при этом он использует полиномиальное пространство.

И хотя этот алгоритм не делает ничего особенно интересного, он демонстрирует один важный принцип: пространство может повторно использоваться в вычислениях, тогда как для времени это по определению невозможно.

А вот более впечатляющее применение этого принципа.

(9.2) Существует алгоритм, решающий задачу 3-SAT с полиномиальными затратами пространства.

Доказательство. Просто используем алгоритм «грубой силы», который перебирает все возможные логические присваивания; каждое присваивание подается на множество условий для проверки того, выполняет ли оно эти условия. Важно реализовать это все с полиномиальными затратами пространства.

Таким образом, полиномиальное пространство выделяется под перебор всех возможных вариантов логического присваивания v.

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

Если условия выполняются, алгоритм можно немедленно остановить. Если условия не выполняются, мы удаляем промежуточные данные, задействованные в этой итерации, и заново используем память для следующего варианта присваивания.

Таким образом, для проверки всех вариантов достаточно полиномиального пространства; тем самым доказывается граница для пространственных затрат алгоритма.