PSPACE - PSPACE: класс задач за пределами NP

До сих пор в этой книге одним из основных вычислительных ресурсов считалось время выполнения. Именно эта концепция стала основой для принятия полиномиального времени как рабочего определения эффективности; и неявно именно она определяет различия между P и NP. В некоторой степени также упоминались требования к пространству (то есть затратам памяти) алгоритмов. В этой главе рассматривается класс задач, который определяет пространство как фундаментальный вычислительный ресурс. Попутно будет разработан естественный класс задач, превышающих по сложности NP и co-NP.

9.1. PSPACE

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

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

(9.1) P ⊆ PSPACE

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

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

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

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

Для этого мы увеличиваем и-разрядный счетчик с 0 до 2ⁿ - 1, как описано выше. Значения счетчика ставятся в соответствие логическим присваиваниям: когда счетчик достигает значения q, оно интерпретируется как присваивание v, при котором x_i содержит значение i-го бита q.

Таким образом, полиномиальное пространство выделяется под перебор всех возможных вариантов логического присваивания v. Для каждого логического присваивания достаточно полиномиального пространства, чтобы подать данные на набор условий и проверить, обеспечивается ли их выполнение. Если условия выполняются, алгоритм можно немедленно остановить. Если условия не выполняются, мы удаляем промежуточные данные, задействованные в этой итерации, и заново используем память для следующего варианта присваивания. Таким образом, для проверки всех вариантов достаточно полиномиального пространства; тем самым доказывается граница для пространственных затрат алгоритма. ■

Так как 3-SAT является NP-полной задачей, у (9.2) имеется одно важное следствие.

(9.3) NP ⊆ PSPACE

Доказательство. Рассмотрим произвольную задачу Y из NP. Так как Y≤_Р 3-SAT, существует алгоритм, который решает Y с полиномиальным количеством шагов плюс полиномиальное количество обращений к “черному ящику” для 3-SAT. Используя алгоритм в (9.2) для реализации “черного ящика”, мы получаем алгоритм для Y, использующий только полиномиальное пространство. ■

Как и в случае с классом Р, задача X принадлежит PSPACE в том, и только в том случае, если ее дополняющая задача также принадлежит PSPACE. Из этого следует, что co-NP ⊆ PSPACE. Структурная диаграмма этих классов задач изображена на рис. 9.1.

Рис. 9.1. Отношения между подмножествами различных классов задач. Учтите, что гипотезы о том, что все эти классы отличны друг от друга, до сих пор не доказаны

Так как PSPACE содержит невероятно огромный класс задач, включая как NP, так и co-NP, весьма вероятно, что в нем присутствуют задачи, которые не решаются за полиномиальное время. Но несмотря на это широко распространенное мнение, как ни удивительно, до сих пор не доказано, что P ≠ PSPACE. Тем не менее почти общепринято мнение, что в PSPACE присутствуют задачи, не входящие даже в NP или co-NP.