Класс NP: сводимость и полнота

NP — класс предикатов, вычислимых за полиномиальное время недетерминированными машинами Тьюринга.

Термин "недетерминированный" неудачный, но он уже стал стандартным.

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

Мы дадим несколько определений этого класса. Первое использует понятие недетерминированной машины Тьюринга. Устройство недетерминированной машины (НМТ) такое же, как и обычной (детерминированной), за одним исключением. У управляющего устройства НМТ есть особые недетерминированные состояния. Находясь в таком состоянии, НМТ может выполнить одно из нескольких действий. Поэтому у НМТ вместо функции переходов есть таблица, в которой для каждой пары (состояние управляющего устройства, текущий символ на ленте) вместо единственно возможного варианта действий (изменение состояния управляющего устройства, запись символа на ленту, сдвиг головки) указан набор возможных действий. Обычные, детерминированные, состояния становятся частным случаем, когда такой набор состоит ровно из одного варианта действий.

Путь вычисления НМТ определяется выбором одного из возможных переходов на каждом такте работы. Недетерминированность приводит к тому, что путей вычисления для НМТ, работающей на данном входном слове, оказывается много.

Определение 2.1. Предикат $$L$$ принадлежит классу $$NP$$, если существуют НМТ $$M$$ и полином $$p(n)$$ такие, что

$$L(x)=1$$ $$\Longrightarrow$$ существует путь вычисления, дающий ответ "да" за время, не превосходящее $$p(|x|)$$ ;

$$L(x)=0$$ $$\Longrightarrow$$ (1 вариант определения ) нет указанного выше пути; (2 вариант определения ) на любом пути вычисления ответа "да" не получается.

Замечание 2.1. Приведенные варианты определения эквивалентны. Чтобы исключить возможность ответов "да" на длинных путях вычисления, достаточно взять НМТ, имитирующую исходную НМТ и подсчитывающую количество сделанных исходной НМТ шагов. Когда число шагов превышает $$p(|x|)$$, машина останавливается.

Замечание 2.2. В предыдущем рассуждении допущена одна тонкая ошибка. В определении ничего не сказано о полиноме $$p(n)$$, кроме факта его существования. Если коэффициенты полинома невычислимы, могут возникнуть проблемы с указанным выше способом сведения одного определения к другому (нужно вычислить значение полинома). Чтобы в дальнейшем избегать этой сложности, будем считать, что полином имеет целые коэффициенты.

Замечание 2.3. Непосредственно из определения 2.1 следует, что $$\P\subseteq\NP$$. Является ли это включение строгим? Довольно интенсивные, хотя и безуспешные, попытки ответить на этот вопрос продолжаются уже почти 30 лет. Недавно С.Смейл включил проблему $$\P\qne\NP$$ в число трех важнейших математических проблем следующего столетия (две другие — гипотеза Римана и гипотеза Пуанкаре).

Второе определение класса NP представляется более естественным. Оно использует понятие полиномиально вычислимого предиката от двух переменных. Определение такого предиката получается комбинацией определений 1.2 и 1.3. Под размером входа для предиката $$R(x,y)$$ можно понимать также или $$|x|+|y|$$, или $$\max(|x|,|y|)$$ — получатся эквивалентные определения.

Определение 2.2. Предикат $$L$$ принадлежит классу NP, если он представим в форме $$L(x)=\exists\, y\:\big( (|y|<q(|x|))\:\wedge\: R(x,y)\big)$$, где $$q(\cdot)$$ — полином, а $$R(\cdot,\cdot)\in\P$$.

Пример 2.1. Пусть $$R(x,y)=$$ " $$y$$ есть гамильтонов цикл в графе $$x$$ ". Более точно нужно сказать так: " $$x$$ есть двоичный код некоторого графа, а $$y$$ — код гамильтонова цикла в этом графе (используем такое кодирование, при котором код цикла не длиннее кода графа), такие что $$\dots$$ ". Возьмем $$q(n)=n$$. Тогда $$L(x)$$ будет в точности означать, что в графе найдется гамильтонов цикл.

Теорема 2.1. Определения 2.1 и 2.2 эквивалентны.

Опр. 2.1 $$\Longrightarrow$$ опр. 2.2. Пусть есть НМТ $$M$$ и полином $$p(n)$$ из первого определения. Рассмотрим предикат $$R(x,y)=$$ " $$y$$ есть протокол работы $$M$$ на возможном пути вычисления со входом $$x$$ дающего ответ "да" за время, не превосходящее $$p(|x|)$$." Длина такого протокола при разумном кодировании линейно зависит от времени вычисления (если использовать в качестве протокола описанную в доказательстве теоремы 1.2 таблицу вычисления, то квадратично), поэтому в качестве $$q(n)$$ для второго определения можно взять $$p(n)$$ ( $$p^2(n)$$ ), умноженный на подходящую константу.

Чтобы закончить доказательство в этом случае, осталось проверить, что $$R(\cdot,\cdot)\in\P$$. Это почти очевидно. Мы должны проверить протокол некоторой НМТ, работающей за полиномиальное время. Это займет нас примерно на то же время (совершенно незачем смотреть на одну ячейку экспоненциально долго).

Опр. 2.2 $$\Longrightarrow$$ опр. 2.1. Пусть есть $$R,q$$ из определения 2.2. Построим $$M$$ для определения 2.1. Она работает в два этапа.

Вначале $$M$$ недетерминированно пишет $$y$$ (который в силу определения 2.2 существует для любого слова $$x$$, для которого $$L(x)=1$$ ). Говорят еще, что $$M$$ "отгадывает" ("guesses") $$y$$. Более точно это означает, что $$M$$ находит правый конец входного слова, сдвигается еще на одну ячейку вправо, записывает в нее $$\#$$, еще раз сдвигается вправо и переходит в такое недетерминированное состояние, в котором она пишет один из символов на ленту, сдвигается вправо и выбирает между сохранением этого состояния и переходом в (уже детерминированное) состояние начала следующего этапа.

После завершения первого этапа на ленте, помимо входного слова $$x$$, записано еще и слово $$y$$. Теперь $$M$$ осталось вычислить значение предиката $$R(x,y)$$ за полиномиальное время. Это можно сделать, используя детерминированный алгоритм, существующий в силу определения 2.2.

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

Определение 2.3. Имеются два персонажа: король A rthur (Артур), умственные способности которого полиномиально ограничены, и волшебник M erlin (Мерлин), который интеллектуально всемогущ и знает правильные ответы на все вопросы. Король A интересуется некоторым свойством $$L(x)$$ (например, "есть ли у графа гамильтонов цикл"), а волшебник M хочет, чтобы король признал наличие этого свойства (ну, скажем, граф стремится к званию гамильтонова и дал M взятку). A не доверяет своему волшебнику, зная его корыстолюбие, и хочет иметь возможность самостоятельно проверить предложенный M ответ.

Поэтому они действуют следующим образом. A и M оба смотрят на слово $$x$$, после чего M сообщает некоторую информацию (слово $$y$$ ), которая должна убедить A, что $$L(x)=1$$. Используя эту информацию, A проверяет убедительность аргументов M некоторым полиномиальным способом.

В этих терминах определение класса NP можно сформулировать так: свойство $$L$$ принадлежит классу NP, если у Артура есть полиномиальный способ проверять убедительность доводов Мерлина, причем:

$$L(x)=1$$ $$\Longrightarrow$$ у M есть способ убедить A в этом;

$$L(x)=0$$ $$\Longrightarrow$$ как бы M ни изощрялся, A не поверит, что $$L(x)=1$$.

Эквивалентность этого определения определению 2.2 не вызывает сомнений. Действительно, из-за полиномиальной ограниченности короля A, сообщение волшебника M должно иметь полиномиальный размер. В остальном различия между определениями чисто внешние.

Сводимость и NP-полнота.

Сложность вычисления предикатов можно сравнивать, пользуясь следующим определением.

Определение 2.4. Сводимость по Карпу. Предикат $$L_1$$ сводится к предикату $$L_2$$ (обозначение $$L_1\propto L_2$$ ), если существует такая функция $$f\in\P$$, что $$\forall\, x\:L_1(x)=L_2(f(x))$$.

Сводимость по Карпу также называют полиномиальной сводимостью, а часто — просто сводимостью.

Лемма 2.1. Пусть $$L_1\propto L_2$$. Тогда

$$L_2\in\P \Rightarrow L_1\in\P$$

$$L_1\not\in\P \Rightarrow L_2\not\in\P$$

$$L_2\in\NP \Rightarrow L_1\in\NP$$.

Доказательство. Пункт 1 совершенно очевиден — чтобы вычислить значение предиката $$L_1$$, достаточно применить ко входу $$x$$ функцию $$f$$, а к результату ее работы — программу вычисления $$L_2$$.

Пункт 2 следует из пункта 1.

Пункт 3 также прост. Его можно объяснять по-разному. Например, так: Мерлин сообщает Артуру $$f(x)$$ (длина которого ограничена некоторым полиномом $$h$$ от длины $$x$$, поскольку $$f\in\P$$ ) и слово $$y$$, которое убеждает Артура в том, что $$L_2(f(x))=1$$. Артур также может проверить, что ему действительно сообщено $$f(x)$$. Используя определение 2.2, можно написать цепочку эквивалентностей$$L_1(x)\Leftrightarrow L_2(f(x)) \Leftrightarrow \exists\, y\: \big( (|y|<q(|f(x)|))\wedge R(f(x),y)\big)\Leftrightarrow\\\Leftrightarrow\exists\, y\: \big( (|y|<r(|x|))\wedge R(f(x),y)\big).$$ Полином $$r(|x|)$$ в последнем выражении — это композиция полиномов $$q$$ и $$h$$.

Определение 2.5. Предикат $$L\in\NP$$ называется NP- полным, если любой предикат из $$\NP$$ к нему сводится.

Если некоторый NP-полный предикат можно вычислять за время $$T(n)$$, то любой предикат из NP можно вычислять за время $$T(n^c)$$ для некоторого фиксированного числа $$c$$. Такая потеря эффективности считается в этой науке несущественной.

NP-полные предикаты существуют, приведем примеры.

Выполнимость. Задается предикатом

$$SAT(x)$$ $$\Longleftrightarrow$$ $$x$$ есть формула с булевыми переменными и символами $$(\neg,\, \vee,\, \wedge)$$, которая истинна при некоторых значениях переменных.

Теорема 2.2 (Кук, Левин). 1) $$SAT\in\NP$$ ; 2) $$SAT$$ — NP- полна.

Если $$SAT\in\P$$, то $$\P=\NP$$.

Доказательство (теоремы 2.2). 1) Мерлину достаточно сообщить Артуру значения переменных, входящих в формулу, при которых она истинна. Артур справится с проверкой истинности полученного высказывания.

2) Пусть предикат из NP, который нужно свести к $$SAT$$, имеет вид $$L(x)= \exists\,y\:\big((|y|<q(|x|)) \wedge R(x,y)\big)$$.

Рассмотрим таблицу вычисления (см. доказательство теоремы 1.2) для МТ, вычисляющей $$R(x,y)$$ (входом является пара $$x\#y$$ ). Будем использовать те же переменные, что и в доказательстве теоремы 1.2 (коды состояний клеток таблицы вычисления). Чтобы таблица вычисления соответствовала правильно проведенному успешному (с ответом "да") вычислению, должны выполняться локальные правила согласования для каждой четверки клеток видаи результат должен быть "да". Каждое такое правило задается формулой от переменных, отвечающих либо рассматриваемой четверке, либо нулевой ячейке самой нижней строки таблицы. Определим формулу $$\varphi_x$$ как конъюнкцию всех этих формул, в которые подставлены значения переменных, кодирующих вход $$x\# y$$, дополненный символами $$\emptycell$$ до длины $$|x|+1+q(|x|)$$. Значения, соответствующие $$x$$ и $$\#$$, — константы, поэтому переменные, от которых зависит эта формула, отвечают $$y$$ и кодам внутренних ячеек таблицы. Так что можно считать, что формула $$\phi_x$$ зависит от $$y$$ и еще от каких-то переменных, которые мы обозначим $$z$$.

Итак, мы сопоставили слову $$x$$ формулу $$\varphi_x(y,z)$$, которая по построению обладает следующим свойством. Если выполняется $$R(x,y)$$, то найдется такой набор значений $$z(x,y)$$, при котором $$\varphi_x(y,z(x,y))$$ истинна (эти значения описывают работу МТ на входе $$x\# y$$ ). А если $$R(x,y)$$ не выполняется, то $$\varphi_x(y,z)$$ всегда ложна (поскольку по сути утверждает, что вычисление на входе $$(x,y)$$ дает ответ "да"). Таким образом, при $$L(x)=1$$ такая формула иногда (при некоторых значениях $$y$$ ) истинна, при $$L(x)=0$$ — всегда ложна.

Другие примеры NP-полных задач получаются с помощью следующей леммы.

Лемма 2.2. Если $$SAT\propto L$$ и $$L\in\NP$$, то $$L$$ — NP-полная. И вообще, если $$L_1$$ — NP-полная, $$L_1\proptoL_2$$ и $$L_2\in\NP$$, то $$L_2$$ — NP-полная.

Доказательство. Достаточно проверить транзитивность сводимости: если $$L_1\propto L_2$$, $$L_2\propto L_3$$, то $$L_1\propto L_3$$. Она следует из того, что композиция двух полиномиально вычислимых функций полиномиально вычислима.

3-КНФ. Задается предикатом

$$3\text{-}SAT(x)$$ $$\Longleftrightarrow$$ $$x$$ есть 3-КНФ, которая истинна истинна при некоторых значениях переменных. 3-КНФ — это конъюнкция дизъюнкций, каждая из которых содержит три литерала.

$$3\text{-}SAT$$ также NP-полна. Это устанавливается сведением к ней $$SAT$$.

Теорема 2.3. $$SAT\propto 3\text{-}SAT$$.

Доказательство. Сопоставим любой схеме в стандартном базисе такую 3-КНФ, выполнимость которой равносильна тому, что вычисляемая схемой функция не равна тождественно 0. В эту КНФ будут входить все переменные схемы ( $$x_1,\dots,x_n$$ и $$y_1,\dots,y_s$$ — используем те же обозначения, что и в определении схемы). Для этого построим вначале конъюнкцию $$K''$$ условий, означающих, что каждая из вспомогательных переменных $$y_j$$ имеет значение, соответствующее правой части присваивания $$Y_j$$. Есть три типа таких условий (они соответстуют трем базисным функциям), и каждый можно записать в виде 3-КНФ:

$$\begin{align*} \big( y\Leftrightarrow( x_1\vee x_2)\big) = (x_1\vee x_2\vee\neg y)\wedge(\neg x_1\vee x_2\vee y)\wedge (x_1\vee\neg x_2\vee y)\wedge\\ \wedge(\neg x_1\vee\neg x_2\vee y),\\ \big(y\Leftrightarrow(x_{1}\wedge x_2)\big)= (x_1\vee x_2\vee\neg y)\wedge(\neg x_1\vee x_2\vee\neg y)\wedge (x_1\vee\neg x_2\vee\neg y)\wedge\\ \wedge(\neg x_1\vee\neg x_2\vee y),\\ \big(y\Leftrightarrow\neg x\big)= (x\vee y)\wedge(\neg x\vee \neg y). \end{align*}$$

Подставляя эти 3-КНФ в $$K''$$, получим 3-КНФ $$K'$$. Искомая 3-КНФ имеет вид $$K=K'\wedge y_s$$. Действительно, истинность $$K$$ равносильна утверждению: все присваивания выполнены правильно и в результате получилась 1 ( $$y_s=1$$ ). Значит, если при каких-то значениях переменных $$x_i$$ схема выдает 1, то $$K$$ выполнима, и наоборот.

Еще один простой пример сведения.

Задача ЦЛП (целочисленного линейного программирования). Дана система линейных неравенств с целыми коэффициентами. Есть ли у нее целочисленное решение? (Другими словами, совместна ли система?)

В этой задаче входом является матрица коэффициентов и вектор правых частей. То, что $$\textsc{ЦЛП}\in \NP$$, не совсем очевидно. Оказывается, что в качестве подсказки Мерлин может сообщить Артуру значения переменных, при которых выполнены все неравенства системы. По определению, длина этого сообщения должна быть также полиномиально ограничена. Можно доказать, что из существования целочисленного решения следует существование целочисленного решения, размер записи которого ограничен полиномом от длины записи системы, см. [14, т. 2, 17.1].

Сведем теперь 3-КНФ к ЦЛП. Построим по 3-КНФ систему линейных неравенств. Целочисленных переменных возьмем столько же, сколько есть булевых переменных. Булевой переменной $$x_i$$ сопоставим выражение $$p_i$$. Отрицанию переменной $$\neg x_i$$ сопоставим выражение $$1-p_i$$. Каждой дизъюнкции $$X_j\vee X_k \vee X_m$$ ( $$X_*$$ — литералы) сопоставим неравенство $$P_j+P_k+P_m\geq1$$, в котором $$P_j$$, $$P_k$$, $$P_m$$ — выражения, сопоставленные литералам дизъюнкции.

Искомая система содержит для всех $$i$$ неравенства $$0\leq p_i\leq 1$$, а также все неравенства, сопоставленные дизъюнкциям из КНФ. Очевидно, что выполнимость 3-КНФ равносильна совместности такой системы.

Замечание 2.4. Если не требовать целочисленности решений, то проверить совместность системы линейных неравенств можно за полиномиальное время. Примеры таких алгоритмов (Хачияна, Кармаркара) также см. в [14, т. 1, 13, 15.1].

Обширный список NP-полных задач содержится в книге Гэри и Джонсона [3]. Как правило, их NP-полнота доказывается с помощью сведений. Приведем несколько примеров NP-полных задач.

3-раскраска. Дан граф. Спрашивается, можно ли раскрасить его вершины в три цвета так, чтобы концы каждого ребра были покрашены в разные цвета. (Аналогичная задача 2-раскраска решается за полиномиальное время.)

Клика. Даны граф и число $$k$$. Спрашивается, есть ли $$k$$ -элементное множество вершин графа, любые две вершины которого соединены ребром.

Задачи

Докажите, что задача проверки выполнимости 2-КНФ (конъюнкции дизъюнкций, каждая из которых содержит два литерала) принадлежит P.

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

Предположим, что класс NP совпадает с P. Докажите, что в этом случае за полиномиальное время можно не только проверить выполнимость формулы, но и найти значения переменных, при которых она истинна (аналогично для гамильтонова цикла и т.п.)

Докажите, что задача о паросочетаниях (есть $$n$$ мальчиков и $$n$$ девочек, известно, какие пары согласны друг с другом танцевать; надо определить, можно ли устроить танец, в котором все $$n$$ мальчиков и $$n$$ девочек соединены в пары) принадлежит NP и, более того, принадлежит P.

Постройте

полиномиальное сведение задачи 3-КНФ к задаче Клика;

тот же вопрос, но дополнительно требуется, чтобы количество решений сохранялось (если 3-КНФ $$F$$ при сведении соответствует пара (граф $$H$$, размер $$k$$ ), то количество выполняющих наборов переменных для $$F$$ равно количеству клик размера $$k$$ в графе $$H$$ ).

Постройте

полиномиальное сведение задачи 3-КНФ к задаче 3-раскраска;

тот же вопрос, но дополнительно требуется, чтобы количество выполняющих наборов переменных для любой 3-КНФ равнялось бы шестикратному количеству 3-раскрасок соответствующего ей графа.

Покажите, что следующая задача является NP-полной: дан набор из не более чем $$n$$ типов квадратиков $$1\times1$$, на сторонах которых написаны какие-то буквы; дан список допустимых пар букв и список граничных букв; спрашивается, можно ли корректно сложить из квадратиков набора большой квадрат размера $$n\times n$$ (так, чтобы на примыкающих сторонах квадратиков были только допустимые пары букв, а на границе квадрата — только граничные буквы).

Докажите, что предикат " $$x$$ — двоичная запись составного числа" принадлежит NP.

Докажите, что предикат " $$x$$ — двоичная запись простого числа" принадлежит NP.