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


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

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

== NP-полнота <tex> \mathrm{BH_{1N}} </tex> ==
<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \le t </tex>.

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

== NP-полнота <tex> \mathrm{SAT} </tex> ==
<tex> \mathrm{SAT}</tex> {{---}} язык булевых формул из <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.

<tex> \mathrm{SAT} = \lbrace \varphi \mid \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
|proof=
# <tex> \mathrm{SAT}\in \mathrm{NP} </tex> <br>Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{SAT}\in \mathrm{NPH} </tex> <br> Теперь докажем, что <tex> \mathrm{SAT}\in \mathrm{NPH} </tex>. Для этого сведём задачу <tex> \mathrm{BH_{1N}} </tex>, которая <tex> \mathrm{NP} </tex>-полна, к <tex> \mathrm{SAT} </tex>. Тогда получится, что любой язык из <tex> \mathrm{NP} </tex> может быть [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведен по Карпу]] к <tex> \mathrm{BH_{1N}} </tex>, и, по транзитивности сведения по Карпу, к <tex> \mathrm{SAT} </tex>. <br> По определению языка <tex> \mathrm{BH_{1N}} </tex>, у нас есть:
#* недетерминированная машина Тьюринга <tex>m</tex>, причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы
#* входное слово <tex>x</tex>
#* время <tex>t</tex>, заданное в унарной системе счисления. 
#:Нам же надо построить такую булеву формулу <tex>\varphi</tex>, что она выполнима тогда, и только тогда, когда <tex>m</tex>, получив на вход <tex>x</tex>, делает не более <tex>t</tex> шагов и допускает это слово. <br> В любой момент времени мгновенное описание (МО) <tex>m</tex> есть строка <tex>z\#_qyb</tex>, где <tex>b</tex> &mdash; строка, состоящая из такого количества пробелов, чтобы длина всего МО была <tex>t + 1.</tex> Соответственно, начальное МО задаётся так: <tex>\#_sxb</tex>. Если же <tex>|x| > t</tex>, то будем считать, что на ленту записаны лишь первые <tex>t</tex> символов, ведь <tex>m</tex> не может обработать большее количество символов за <tex>t</tex> шагов. <br> Также нам удобно считать, что все вычисления проходят ровно за <tex>t + 1</tex> шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход <tex>q \vdash q</tex>, если в МО <tex>q</tex> есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО <tex>q_t</tex>. <br> Тогда процесс работы машины <tex>m</tex> на входе <tex>x</tex>, то есть цепочка переходов <tex>q_0 \vdash q_1 \vdash \ldots \vdash q_t</tex> может быть представлен следующей таблицей : 
<table align="right" border="1" style="text-align:center" cellspacing="0">
<tr> 
<td colspan=10>
'''Процесс работы машины <tex>m</tex> на входе <tex>x</tex>''' 
</td>
</tr>
<tr> 
<td width="50"> 
MO 
</td> 
<td width="50" > 
0 
</td> 
<td width="50"> 
1 
</td> 
<td  width="30">
... 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="30">
... 
</td> 
<td width="50">
t 
</td>
</tr>
<tr> 
<td width="50"> 
<tex>q_0</tex>
</td> 
<td width="50" > 
<tex>q_{0, 0}</tex>
</td> 
<td width="50"> 
<tex>q_{0, 1}</tex>
</td> 
<td  width="30">
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="30">
</td> 
<td width="50">
<tex>q_{0, t}</tex>
</td>
</tr>
<tr> 
<td width="50"> 
<tex>q_1</tex>
</td> 
<td width="50" > 
<tex>q_{1, 0}</tex>
</td> 
<td width="50"> 
<tex>q_{1, 1}</tex>
</td> 
<td  width="30">
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="30">
</td> 
<td width="50">
<tex>q_{1, t}</tex>
</td>
</tr>
<tr> 
<td width="50"> 
...
</td> 
<td width="50" > 
</td> 
<td width="50"> 
</td> 
<td  width="30">
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="30">
</td> 
<td width="50">
</td>
</tr>
<tr> 
<td width="50"> 
<tex> q_i </tex>
</td> 
<td width="50" > 
</td> 
<td width="50"> 
</td> 
<td  width="30">
</td>
<td width="50"> 
<tex> q_{i, j - 1} </tex>
</td>
<td width="50"> 
<tex> q_{i, j} </tex>
</td>
<td width="50"> 
<tex> q_{i, j + 1} </tex>
</td>
<td width="50">
<tex> q_{i, j + 2} </tex> 
</td>
<td width="30">
</td> 
<td width="50">
</td>
</tr>
<tr> 
<td width="50"> 
<tex> q_{i+1} </tex>
</td> 
<td width="50" > 
</td> 
<td width="50"> 
</td> 
<td  width="30">
</td>
<td width="50"> 
<tex> q_{i+1, j - 1} </tex>
</td>
<td width="50"> 
<tex> q_{i+1, j} </tex>
</td>
<td width="50"> 
<tex> q_{i+1, j + 1} </tex>
</td>
<td width="50">
</td>
<td width="30">
</td> 
<td width="50">
</td>
</tr>
<tr> 
<td width="50"> 
...
</td> 
<td width="50" > 
</td> 
<td width="50"> 
</td> 
<td  width="30">
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="30">
</td> 
<td width="50">
</td>
</tr>
<tr> 
<td width="50"> 
<tex>q_t</tex>
</td> 
<td width="50" > 
<tex>q_{t, 0}</tex>
</td> 
<td width="50"> 
<tex>q_{t, 1}</tex>
</td> 
<td  width="30">
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="50"> 
</td>
<td width="30">
</td> 
<td width="50">
<tex>q_{t, t}</tex>
</td>
</tr>
</table>

::Каждый элемент таблицы <tex>q_{i, j}\in \Sigma \cup Q</tex>. И для каждого такого элемента заведём <tex>|\Sigma| + |Q|</tex> переменных <tex>Y_{i, j, c} = [q_{i, j} = c]\ \forall c \in \Sigma \cup Q</tex> <br> Общий вид формулы: <tex>\varphi = S \land T \land N \land C</tex>. 
::# <tex>S</tex> отвечает за правильный старт, то есть символ <tex>q_{0,0}</tex> должен быть начальным состоянием <tex>\#_s</tex> машины <tex>m</tex>, символы с <tex>q_{0,1}</tex> по <tex>q_{0,|x|}</tex> &mdash; образовывать цепочку <tex>x</tex>, а оставшиеся <tex>q_{0,i}</tex> &mdash; быть пробелами <tex>B</tex>. Таким образом, <tex>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}</tex>.
::# <tex>T</tex> отвечает за правильный финиш, то есть в МО <tex>q_t</tex> должно присутствовать допускающее состояние <tex>\#_y</tex>, следовательно <tex>T = Y_{t,0,\#_y} \lor Y_{t,1,\#_y} \lor \ldots \lor Y_{t,t,\#_y}</tex>.
::# <tex>N</tex> отвечает за то, что машина <tex>m</tex> делает правильные переходы. <tex>q_{i,j}</tex> зависит только от четырех символов над ним, то есть от <tex>q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex>. Тогда для проверки корректности переходов требуется перебрать все четверки символов <tex>q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex> из таблицы и проверить, что из них возможно получить символ <tex>q_{i,j}</tex>. Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. С учетом того, что машина <tex>m</tex> недетерминирована и требуется устранить возможность раздвоения ее головки, сделаем все возможные выводы о новых символах <tex>q_{i,j \pm 1}</tex>: <br> <tex>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}^`})))</tex>.
::# <tex>C</tex> отвечает за то, что в каждой ячейке находится ровно один символ. Для каждой ячейки <tex>q_{i,j}</tex> проверяется, что только одна переменная <tex>Y_{i,j,c}</tex> принимает значение ''истина''.<br> <tex>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}}))</tex>.
:: Мы построили функцию сведения <tex> f: \langle m, x, 1^t \rangle \mapsto \varphi = S \land T \land N \land C</tex>. Она является полиномиальной, так как длина формулы <tex>\varphi</tex> полиномиально зависит от длины входа &mdash; <tex>|\varphi| = O(n^2)</tex>. <br> Покажем, что <tex>\varphi</tex> выполнима тогда и только тогда, когда <tex>\langle m, x, 1^t \rangle \in  \mathrm{BH_{1N}} </tex>.
:# Пусть <tex>\langle m, x, 1^t \rangle \in  \mathrm{BH_{1N}}</tex>, тогда существует допускающая цепочка переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex> и можем построить таблицу, аналогичную приведенной выше, следовательно можем найти такое присваивание 0 и 1 переменным <tex>Y_{i,j,c}</tex>, что <tex>\varphi</tex> примет значение ''истина''.
:# Пусть в результате работы функции <tex>f</tex> получили выполнимую формулу <tex>\varphi</tex>, следовательно существует такой набор переменных <tex>Y_{i,j,c}</tex>, что <tex>\varphi</tex> на нем принимает значение ''истина''. Тогда по данному набору можем построить таблицу, по которой восстановим допускающую цепочку переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex>. Совершив эти переходы машина <tex>m</tex> перейдет в допускающее состояние за время <tex>t</tex>, следовательно <tex>\langle m, x, 1^t\rangle \in  \mathrm{BH_{1N}}</tex>.

:Значит <tex> \mathrm{SAT} \in \mathrm{NPC} </tex>, что и требовалось доказать.

}}

== Другие примеры NP-полных языков ==
=== NP-полнота CNFSAT ===
<tex> \mathrm{CNFSAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что для них существует подстановка, при которой формула истинна. 

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

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


:Значит <tex> \mathrm{CNFSAT} \in \mathrm{NPC} </tex>.
}}
=== NP-полнота 3-SAT ===
<tex> \mathrm{3SAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна. 

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

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

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

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

<tex> \mathrm{VCOVER} </tex> {{---}} язык неориентированных графов, таких что в графе есть вершинное покрытие мощности <tex> k </tex>.

<tex> \mathrm{VCOVER} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) : \forall vu \in E(G), (v \in H) \lor (u \in H) \rbrace </tex>
{{Лемма
|statement = <tex> G </tex> {{---}} неориентированный граф. <tex> H \subset G </tex> является независимым множеством в <tex> G \Rightarrow  G \setminus H </tex> является вершинным покрытием в <tex> G </tex>.
|proof=
* <tex> \Rightarrow </tex>
Пусть <tex> H </tex> {{---}} независимое множество. Заметим, что по определению независимого множества <tex> \forall vu \in E(G) : (v \notin H) \lor (u \notin H) </tex>, из чего следует, что <tex> (v \in (G \setminus H)) \lor (u \in (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} вершинное покрытие.
* <tex> \Leftarrow </tex>
Пусть <tex> H </tex> {{---}} вершинное покрытие. Заметим, что <tex> \forall vu \in E(G) : (v \in H) \lor (u \in H) </tex>, из чего следует, что <tex> (v \notin (G \setminus H)) \lor (u \notin (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} независимое множество.
}}

{{Теорема
|statement= <tex> \mathrm{VCOVER} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{VCOVER} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{VCOVER} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество вершинным покрытием, это можно сделать за полином, и выдавать ответ.
# <tex> \mathrm{VCOVER} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{IND} </tex> к задаче <tex> \mathrm{VCOVER} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить паре <tex> \langle G, k \rangle </tex>, пару <tex> \langle H, l \rangle </tex>, такую что <tex> x \in \mathrm{IND} \Leftrightarrow f(x) \in \mathrm{VCOVER} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> <tex> f(\langle G, k \rangle) = \langle G, |V(G)| - k \rangle </tex> <br> Из доказанной выше леммы, следует, что <tex> \langle G, k \rangle \in \mathrm{IND} \Leftrightarrow \langle G, |V(G)| - k \rangle \in \mathrm{VCOVER} </tex>
}}


== Ссылки ==
* [[Класс P]]
* [[Классы NP и Σ₁]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
* [http://en.wikipedia.org/wiki/List_of_NP-complete_problems Список NP-полных задач]
[[Категория: Теория сложности]]