Примеры NP-полных языков. Теорема Кука

Эта статья находится в разработке!

Введение

В этой статье мы рассмотрим класс [math]\mathrm{NP}[/math]-полных языков — [math]\mathrm{NPC}[/math]. [math]\mathrm{NPC}[/math] является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс [math]\mathrm{P}[/math], тогда окажется, что [math]\mathrm{P} = \mathrm{NP}[/math].

Мы рассмотрим некоторые языки и докажем их [math]\mathrm{NP}[/math]-полноту. Начнем мы с языка [math] \mathrm{BH_{1N}} [/math], так как к нему несложно сводятся все языки из [math]\mathrm{NP}[/math]. Потом с помощью сведений по Карпу будем сводить уже известные языки из [math]\mathrm{NPC}[/math] к новым языкам, тем самым доказывая их [math]\mathrm{NP}[/math]-трудность, а потом и [math]\mathrm{NP}[/math]-полноту. Доказательство [math]\mathrm{NP}[/math]-полноты будет состоять из двух пунктов: доказательство [math]\mathrm{NP}[/math]-трудности и принадлежности языка классу [math]\mathrm{NP}[/math].

NP-полнота [math] \mathrm{BH_{1N}} [/math]

[math] \mathrm{BH_{1N}} [/math] — язык троек [math] \langle m, x, 1^t \rangle [/math], таких что недетерминированная машина Тьюринга [math] m [/math] на входной строке [math] x [/math] возращает [math]1[/math] за время [math] T(m, x) \le t [/math].

[math] \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m [/math] — недетерминированная машина Тьюринга, [math] m(x) = 1, T(m,x) \le t \rbrace [/math]

Теорема:

[math] \mathrm{BH_{1N}} \in \mathrm{NPC} [/math]

Доказательство:

[math]\triangleright[/math]

[math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math] Нужно доказать, что [math] \forall \mathrm{L} \in \mathrm{NP} [/math] существует полиномиальное сведение по Карпу к языку [math] \mathrm{BH_{1N}} [/math]. Рассмотрим произвольный язык [math] \mathrm{L} \in \mathrm{NP} [/math]. Для него существует машина Тьюринга [math] m [/math] и полином [math] p(x) [/math], такие что [math] T(m, x) \le p(|x|), \mathrm{L}(m) = \mathrm{L} [/math]. Докажем, что [math] \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} [/math]. Рассмотрим функцию [math] f(x) = \langle m, x, 1^{p(|x|)} \rangle [/math], по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени [math] p(|x|)[/math] в унарной системе счисления. Проверим, что [math] x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} [/math]. Пусть [math] x \in L [/math]. Тогда [math] m(x) = 1 [/math] за время не более [math] p(|x|) [/math], а значит [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} [/math]. Пусть [math]x \not\in L[/math]. Тогда [math]m(x) = 0[/math] и [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} [/math]. Это значит, что [math] \forall \mathrm{L} \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} [/math], и из этого следует, что [math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math]. [math] \mathrm{BH_{1N}} \in \mathrm{NP} [/math] Можно написать недетерминированную программу, которая будет по [math] \langle m, x, 1^t \rangle [/math] моделировать [math] t [/math] шагов [math] m [/math] на входе [math] x [/math], выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда [math] \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} [/math].

[math]\triangleleft[/math]

NP-полнота [math] \mathrm{SAT} [/math]

[math] \mathrm{SAT}[/math] — язык булевых формул из [math] n [/math] переменных, для которых существует подстановка, при которой формула истинна.

[math] \mathrm{SAT} = \lbrace \varphi \mid \exists x : \varphi(x) = 1 \rbrace [/math]

Теорема (Кук):

[math] \mathrm{SAT}\in \mathrm{NPC} [/math]

Доказательство:

[math]\triangleright[/math]

[math] \mathrm{SAT}\in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ. [math] \mathrm{SAT}\in \mathrm{NPH} [/math] Теперь докажем, что [math] \mathrm{SAT}\in \mathrm{NPH} [/math]. Для этого сведём задачу [math] \mathrm{BH_{1N}} [/math], которая [math] \mathrm{NP} [/math]-полна, к [math] \mathrm{SAT} [/math]. Тогда получится, что любой язык из [math] \mathrm{NP} [/math] может быть сведен по Карпу к [math] \mathrm{BH_{1N}} [/math], и, по транзитивности сведения по Карпу, к [math] \mathrm{SAT} [/math]. По определению языка [math] \mathrm{BH_{1N}} [/math], у нас есть недетерминированная машина Тьюринга [math]m[/math], причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы, входное слово [math]x[/math] и время [math]t[/math], заданное в унарной системе счисления. Нам же надо построить такую булеву формулу [math]\varphi[/math], что она выполнима тогда, и только тогда, когда [math]m[/math], получив на вход [math]x[/math], делает не более [math]t[/math] шагов и допускает это слово. В любой момент времени мгновенное описание (МО) [math]m[/math] есть строка [math]z\#_qyb[/math], где [math]b[/math] — строка, состоящая из такого количества пробелов, чтобы длина всего МО была [math]t + 1.[/math] Соответственно, начальное МО задаётся так: [math]\#_sxb[/math]. Если же [math]|x| \gt t[/math], то будем считать, что на ленту записаны лишь первые [math]t[/math] символов, ведь [math]m[/math] не может обработать большее количество символов за [math]t[/math] шагов. Также нам удобно считать, что все вычисления проходят ровно за [math]t + 1[/math] шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход [math]q \vdash q[/math], если в МО [math]q[/math] есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО [math]q_t[/math]. Тогда процесс работы машины [math]m[/math] на входе [math]x[/math], то есть цепочка переходов [math]q_0 \vdash q_1 \vdash \ldots \vdash q_t[/math] может быть представлен следующей таблицей : Процесс работы машины [math]m[/math] на входе [math]x[/math] MO 0 1 ... ... t [math]q_0[/math] [math]q_{0, 0}[/math] [math]q_{0, 1}[/math] [math]q_{0, t}[/math] [math]q_1[/math] [math]q_{1, 0}[/math] [math]q_{1, 1}[/math] [math]q_{1, t}[/math] ... [math] q_i [/math] [math] q_{i, j - 1} [/math] [math] q_{i, j} [/math] [math] q_{i, j + 1} [/math] [math] q_{i, j + 2} [/math] [math] q_{i+1} [/math] [math] q_{i+1, j - 1} [/math] [math] q_{i+1, j} [/math] [math] q_{i+1, j + 1} [/math] ... [math]q_t[/math] [math]q_{t, 0}[/math] [math]q_{t, 1}[/math] [math]q_{t, t}[/math] Каждый элемент таблицы [math]q_{i, j}\in \Sigma \cup Q[/math]. И для каждого такого элемента заведём [math]|\Sigma| + |Q|[/math] переменных [math]Y_{i, j, c} = [q_{i, j} = c]\ \forall c \in \Sigma \cup Q[/math] Общий вид формулы: [math]\varphi = S \land T \land N \land C[/math]. [math]S[/math] отвечает за правильный старт, то есть символ [math]q_{0,0}[/math] должен быть начальным состоянием [math]\#_s[/math] машины [math]m[/math], символы с [math]q_{0,1}[/math] по [math]q_{0,|x|}[/math] — образовывать цепочку [math]x[/math], а оставшиеся [math]q_{0,i}[/math] — быть пробелами [math]B[/math]. Таким образом, [math]S = Y_{0,0,\#_s} \land Y_{0,1,x_1} \land \ldots \land Y_{0,|x|+1,B} \land \ldots \land Y_{0,t,B}[/math]. [math]T[/math] отвечает за правильный финиш, то есть в МО [math]q_t[/math] должно присутствовать допускающее состояние [math]\#_y[/math], следовательно [math]T = Y_{t,0,\#_y} \lor Y_{t,1,\#_y} \lor \ldots \lor Y_{t,t,\#_y}[/math]. [math]N[/math] отвечает за то, что машина [math]m[/math] делает правильные переходы. [math]q_{i,j}[/math] зависит только от четырех символов над ним, то есть от [math]q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}[/math] и [math]q_{i-1,j+2}[/math]. Тогда для проверки корректности переходов требуется перебрать все четверки символов [math]q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}[/math] и [math]q_{i-1,j+2}[/math] из таблицы и проверить, что из них возможно получить символ [math]q_{i,j}[/math]. Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. С учетом того, что машина [math]m[/math] недетерминирована и требуется устранить возможность раздвоения ее головки, сделаем все возможные выводы о новых символах [math]q_{i,j \pm 1}[/math]: [math]N = \land_{i=0..t,j=0..t} \land_{c_1 \ldots c_4} (( Y_{i-1,j-1,c_1} \land Y_{i-1,j,c_2} \land Y_{i-1,j+1,c_3} \land Y_{i-1,j+2,c_4} ) \to ((Y_{i,j-1,c_0^`} \lor Y_{i,j-1,c_1^`} \lor \ldots \lor Y_{i,j-1,c_{|\Sigma|+|Q|-1}^`}) \land (Y_{i,j,c_0^`} \lor Y_{i,j,c_1^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|+|Q|-1}^`}) \land (Y_{i,j+1,c_0^`} \lor Y_{i,j+1,c_1^`} \lor \ldots \lor Y_{i,j+1,c_{|\Sigma|+|Q|-1}^`})))[/math]. [math]C[/math] отвечает за то, что в каждой ячейке находится ровно один символ. Для каждой ячейки [math]q_{i,j}[/math] проверяется, что только одна переменная [math]Y_{i,j,c}[/math] принимает значение истина. [math]C = \land_{i=0..t,j=0..t} ((Y_{i,j,c_1} \land \lnot Y_{i,j,c_2} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|+|Q|-1}}) \lor \ldots \lor (Y_{i,j,c_{|\Sigma|+|Q|-1}} \land \lnot Y_{i,j,c_1} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|+|Q|-2}}))[/math]. Мы построили функцию сведения [math] f: \langle m, x, 1^t \rangle \mapsto \varphi = S \land T \land N \land C[/math]. Она является полиномиальной, так как длина формулы [math]\varphi[/math] полиномиально зависит от длины входа — [math]|\varphi| = O(n^2)[/math]. Покажем, что [math]\varphi[/math] выполнима тогда и только тогда, когда [math]\langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} [/math]. Пусть [math]\langle m, x, 1^t \rangle \in \mathrm{BH_{1N}}[/math], тогда существует допускающая цепочка переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math] и можем построить таблицу, аналогичную приведенной выше, следовательно можем найти такое присваивание 0 и 1 переменным [math]Y_{i,j,c}[/math], что [math]\varphi[/math] примет значение истина. Пусть в результате работы функции [math]f[/math] получили выполнимую формулу [math]\varphi[/math], следовательно существует такой набор переменных [math]Y_{i,j,c}[/math], что [math]\varphi[/math] на нем принимает значение истина. Тогда по данному набору можем построить таблицу, по которой восстановим допускающую цепочку переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math]. Совершив эти переходы машина [math]m[/math] перейдет в допускающее состояние за время [math]t[/math], следовательно [math]\langle m, x, 1^t\rangle \in \mathrm{BH_{1N}}[/math]. Значит [math] \mathrm{SAT} \in \mathrm{NPC} [/math], что и требовалось доказать.

[math]\triangleleft[/math]

Другие примеры NP-полных языков

NP-полнота CNFSAT

[math] \mathrm{CNFSAT} [/math]— язык булевых формул, заданных в КНФ, таких что для них существует подстановка, при которой формула истинна.

[math] \mathrm{CNFSAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi [/math] задано в КНФ и [math] \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace [/math]

Теорема:

[math] \mathrm{CNFSAT} \in \mathrm{NPC} [/math]

Доказательство:

[math]\triangleright[/math]

[math] \mathrm{CNFSAT} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{CNFSAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ. [math] \mathrm{CNFSAT} \in \mathrm{NPH} [/math] Сведем задачу [math] \mathrm{SAT} [/math] к задаче [math] \mathrm{CNFSAT} [/math]. Построим функцию [math] f(x) [/math], которая будет строить по булевой формуле, булевую формулу в КНФ, такую что [math] x \in \mathrm{SAT} \Leftrightarrow f(x) \in \mathrm{CNFSAT} [/math], причем [math] |f(x)| \le p(|x|) [/math] для некоторого полинома [math] p [/math]. Опишем как будет работать функция [math] f [/math]. Для начала преобразуем формулу так, чтобы все отрицания относились только к переменным. Это можно сделать по правилам: [math] \neg{(x \lor y)} = \neg{x} \land \neg{y} [/math] [math] \neg{(x \land y)} = \neg{x} \lor \neg{y} [/math] Далее построим дерево по формуле [math] x [/math]. Будем строить формулу в КНФ для поддеревьев рекурсивно. Есть два случая: Корень дерева — [math] \land [/math]. Пусть левое и правое поддерево [math] x [/math] — это [math] x_l [/math] и [math] x_r [/math] соответственно. Тогда [math] f(x) = f(x_l) \land f(x_r) [/math]. Корень дерева — [math] \lor [/math]. Пусть левое и правое поддерево [math] x [/math] — это [math] x_l [/math] и [math] x_r [/math] соответственно. Создадим новую переменную [math] z [/math]. Тогда [math] f(x) = (f(x_l) \lor z) \land (f(x_r) \lor \neg{z}) [/math]. [math] f(x_l) [/math] и [math] f(x_r) [/math] — формулы в КНФ, поэтому переменную [math] z [/math] и ее отрицание можно внести в каждую скобку в [math] f(x_l) [/math] и [math] f(x_r) [/math]. Посчитаем какой длины будет [math] f(x) [/math]. Это зависит от количества логических операций в формуле. Заметим, что количество скобок в конечной формуле равно количеству операций [math] \land [/math]. Количество операций [math] \land [/math] не более чем [math] |x| [/math], так как [math] \land [/math] добавляется один раз в первом из рассмотренных выше случаев. А во втором из рассмотренных случаев добавляется [math] \lor [/math] в том количестве, сколько скобок у нас есть. А количество скобок равно количеству [math] \land [/math], поэтому количество операций [math] \lor [/math] не превысит [math] |x|^2 [/math]. Поэтому [math] f [/math] будет работать за полином. Значит [math] \mathrm{CNFSAT} \in \mathrm{NPC} [/math].

[math]\triangleleft[/math]

NP-полнота 3-SAT

[math] \mathrm{3SAT} [/math]— язык булевых формул, заданных в КНФ, таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна.

[math] \mathrm{3SAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi [/math] задано в 3КНФ и [math] \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace [/math]

Теорема:

[math] \mathrm{3SAT} \in \mathrm{NPC} [/math]

Доказательство:

[math]\triangleright[/math]

[math] \mathrm{3SAT} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{3SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ. [math] \mathrm{3SAT} \in \mathrm{NPH} [/math] Сведем задачу [math] \mathrm{CNFSAT} [/math] к задаче [math] \mathrm{3SAT} [/math]. Построим функцию [math] f(x) [/math], которая будет строить по булевой формуле в КНФ, булевую формулу в 3-КНФ, такую что [math] x \in \mathrm{CNFSAT} \Leftrightarrow f(x) \in \mathrm{3SAT} [/math], причем [math] |f(x)| \le p(|x|) [/math] для некоторого полинома [math] p [/math]. Опишем как будет работать функция [math] f [/math]. Заменим каждый дизъюнкт в [math] x [/math] на может быть несколько дизъюнктов, которые состоят ровно из трех переменных. Дизъюнкт содержит не более трех переменных. Тогда возьмем какую-нибудь переменную из этого дизъюнкта и продублируем ее так, чтобы в нем стало ровно 3 переменных. Например: [math] f(y \lor z) = (y \lor z \lor y) [/math], [math] f(y) = (y \lor y \lor y) [/math] Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: [math] (x_1 \lor x_2 \lor \ldots \lor x_k) [/math], создадим новые переменные [math] z_1, z_2, \ldots, z_{k - 2} [/math], и тогда [math] f(x_1 \lor x_2 \lor \ldots \lor x_k) = (x_1~\lor~x_2~\lor~z_1)~\land~(x_3~\lor~\neg{z_1}~\lor~z_2)~\land~\ldots~\land~(x_i~\lor~\neg{z_{i - 2}}~\lor~z_{i - 1})~\land~\ldots~\land~(x_{k - 1}~\lor~x_k~\lor~\neg{z_{k - 2}}) [/math] Можно заметить, что если какое-то [math] x_i = 1 [/math], то существует подстановка для [math] z_1, z_2, \ldots, z_{k - 1} [/math], такая что [math] f(x_1 \lor x_2 \lor \ldots \lor x_k)[/math] удовлетворима. Также, если [math] \forall i : x_i = 0 [/math], нельзя удовлетворить все скобки, так как каждая скобка удовлетворяется только переменными [math] z_1, z_2, \ldots, z_{k - 2} [/math], можно понять, что при выборе значения [math] z_1 [/math] все переменные восстанавливаются однозначно и значение [math] z_{k - 2} [/math] нельзя выбрать так, чтобы удовлетворить последние две скобки одновременно. А значит [math] x \in CNFSAT \Leftrightarrow f(x) \in 3SAT [/math]. Заметим, что размер формулы возрос не более чем в три раза, поэтому функция [math] f [/math] будет работать за полином. Значит [math] \mathrm{3SAT} \in \mathrm{NPC} [/math]

[math]\triangleleft[/math]

NP-полнота поиска максимального независимого множества

[math] \mathrm{IND} [/math]— язык неориентированных графов, таких что в графе есть независимое множество величины [math] k [/math].

[math] \mathrm{IND} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) [/math], такое что [math] H [/math] независимо в [math] G \rbrace [/math]

Теорема:

[math] \mathrm{IND} \in \mathrm{NPC} [/math]

Доказательство:

[math]\triangleright[/math]

[math] \mathrm{IND} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{IND} [/math]. Она будет недетерминированно выбирать множество вершин мощности [math] k [/math], проверять, является ли это множество независимым, это можно сделать за полином, и выдавать ответ. [math] \mathrm{IND} \in \mathrm{NPH} [/math] Сведем задачу [math] \mathrm{3SAT} [/math] к задаче [math] \mathrm{IND} [/math]. Построим функцию [math] f(x) [/math], которая будет строить по булевой формуле в 3-КНФ, пару [math] \langle G, k \rangle [/math], такую что [math] x \in \mathrm{3SAT} \Leftrightarrow f(x) \in \mathrm{IND} [/math], причем [math] |f(x)| \le p(|x|) [/math] для некоторого полинома [math] p [/math]. Опишем как будет работать функция [math] f [/math]. [math] k [/math] — количество дизъюнктов в [math] x [/math]. Для каждого дизъюнкта создадим по три вершины в графе [math] G [/math], каждая из которой будет сопоставлена переменной из этого дизъюнкта. [math] |V(G)| = 3k [/math] Соединим вершины из одного дизъюнкта ребрами. Для всех пар вершин, которые сопоставлены переменным, которые являются отрицаниями друг друга, добавим ребро между этими вершинами. Докажем, что [math] x \in \mathrm{3SAT} \Leftrightarrow \langle G, k \rangle \in \mathrm{IND} [/math] Пусть формула [math] x [/math] удовлетворима. Тогда в каждом дизъюнкте будет будет существовать вершина, что сопоставленная ей переменная истинна. Для каждого дизъюнкта выберем ровно одну такую вершину. Это множество будет мощности [math] k [/math] и независимым, потому что в каждом дизъюнкте мы выбрали ровно одну переменную и мы не выбрали пару вершин, которые сопоставленны переменным, которые являются отрицаниями друг друга. Пусть существует независимое множество мощности [math] k [/math] в графе [math] G [/math]. Тогда известно, что для каждого дизъюнкта не может быть выбрано более одной вершины из нее, значит из каждого дизъюнкта выбрана ровно одна вершина, потому что всего вершин — [math] k [/math]. Теперь если мы удовлетворим каждую переменную, сопоставленная вершина которой в независимом множестве, вся формула удовлетворится. А каждую переменную можно удовлетворить, потому что в независимом множестве нет пары вершин, которым сопоставлены переменные, которые являются отрицаниями друг друга. Значит формула удовлетворима. А значит [math] \mathrm{IND} \in \mathrm{NPC} [/math].

[math]\triangleleft[/math]

Ссылки

• Класс P
• Классы NP и Σ₁
• Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
• Список NP-полных задач