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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 7 участников)
Строка 1: Строка 1:
{{В разработке}}
 
  
 
== Введение ==
 
== Введение ==
В этой статье мы рассмотрим класс '''NP'''-полных языков {{---}} '''NPC'''.
+
В этой статье мы рассмотрим класс <tex>\mathrm{NP}</tex>-полных языков {{---}} <tex>\mathrm{NPC}</tex>.
'''NPC''' является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс '''P''',  
+
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</tex>,  
тогда окажется, что '''P = NP'''.
+
тогда окажется, что <tex>\mathrm{P} = \mathrm{NP}</tex>.
  
Мы рассмотрим некоторые языки и докажем их '''NP'''-полноту. Начнем мы с языка <tex> \mathrm{BH_{1N}} </tex>, так как к нему несложно сводятся все языки из '''NP'''.  
+
Мы рассмотрим некоторые языки и докажем их <tex>\mathrm{NP}</tex>-полноту. Начнем мы с языка <tex> \mathrm{BH_{1N}} </tex>, так как к нему несложно сводятся все языки из <tex>\mathrm{NP}</tex>.  
Потом с помощью [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведений по Карпу]] будем сводить уже известные языки из '''NPC''' к новым языкам, тем самым доказывая их '''NP'''-трудность, а потом и '''NP'''-полноту.
+
Потом с помощью [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведений по Карпу]] будем сводить уже известные языки из <tex>\mathrm{NPC}</tex> к новым языкам, тем самым доказывая их <tex>\mathrm{NP}</tex>-трудность, а потом и <tex>\mathrm{NP}</tex>-полноту.
Доказательство '''NP'''-полноты будет состоять из двух пунктов: доказательство '''NP'''-трудности и принадлежности языка классу '''NP'''.
+
Доказательство <tex>\mathrm{NP}</tex>-полноты будет состоять из двух пунктов: доказательство <tex>\mathrm{NP}</tex>-трудности и принадлежности языка классу <tex>\mathrm{NP}</tex>.
  
 
== NP-полнота <tex> \mathrm{BH_{1N}} </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> возращает '''1''' за время <tex> T(m, x) \le t </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>
+
<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>
 
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC} </tex>
 
|proof=
 
|proof=
# <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>
+
# <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>
+
# <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>.
 
}}
 
}}
  
Строка 24: Строка 23:
 
<tex> \mathrm{SAT}</tex> {{---}} язык булевых формул из <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.
 
<tex> \mathrm{SAT}</tex> {{---}} язык булевых формул из <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.
  
<tex> \mathrm{SAT} = \lbrace \varphi\ \bigm|\ \exists x : \varphi(x) = 1 \rbrace </tex>
+
<tex> \mathrm{SAT} = \lbrace \varphi \mid \exists x : \varphi(x) = 1 \rbrace </tex>
 
{{Теорема
 
{{Теорема
 
|author=Кук
 
|author=Кук
 
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
 
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
 
|proof=
 
|proof=
# <tex> \mathrm{SAT}\in \mathrm{NPH} </tex>
+
# <tex> \mathrm{SAT}\in \mathrm{NP} </tex> <br>Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <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>, у нас есть:
<font size = 2>
+
#* недетерминированная машина Тьюринга <tex>m</tex>, причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы
  <tex>p(\varphi)</tex>
+
#* входное слово <tex>x</tex>
    for <tex> i \in \lbrace 1 \ldots n \rbrace </tex>:
+
#* время <tex>t</tex>, заданное в унарной системе счисления.
      <tex> x_i </tex> = choose<tex> \lbrace 0, 1 \rbrace </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> может быть представлен следующей таблицей :
    if <tex> \varphi(x) </tex> == 1:
+
<table align="right" border="1" style="text-align:center" cellspacing="0">
      return 1
+
<tr>
    else
+
<td colspan=10>
      return 0
+
'''Процесс работы машины <tex>m</tex> на входе <tex>x</tex>'''
</font>
+
</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-полных языков ==
 +
=== 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 ===
 
=== NP-полнота 3-SAT ===
=== NP-полнота раскраски графа ===
+
<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-полнота поиска минимального вершинного покрытия в графе ===
 
=== NP-полнота поиска минимального вершинного покрытия в графе ===
=== NP-полнота поиска максимальной клики в графе ===
+
 
=== NP-полнота поиска гамильтонова цикла и пути в графе ===
+
<tex> \mathrm{VCOVER} </tex> {{---}} язык неориентированных графов, таких что в графе есть вершинное покрытие мощности <tex> k </tex>.
=== NP-полнота задачи о рюкзаке ===
+
 
 +
<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]]
 
* [[Класс P]]
* [[Недетерминированные вычисления. Классы NP и Σ₁]]
+
* [[Классы NP и Σ₁]]
 
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 +
* [http://en.wikipedia.org/wiki/List_of_NP-complete_problems Список NP-полных задач]
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]

Текущая версия на 19:07, 4 сентября 2022

Введение

В этой статье мы рассмотрим класс [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]
  1. [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].

  2. [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]
  1. [math] \mathrm{SAT}\in \mathrm{NP} [/math]
    Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
  2. [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].
  1. [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].
  2. [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].
  3. [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].
  4. [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].
  1. Пусть [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] примет значение истина.
  2. Пусть в результате работы функции [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]
  1. [math] \mathrm{CNFSAT} \in \mathrm{NP} [/math]
    Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{CNFSAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
  2. [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].
    1. Для начала преобразуем формулу так, чтобы все отрицания относились только к переменным. Это можно сделать по правилам:
      • [math] \neg{(x \lor y)} = \neg{x} \land \neg{y} [/math]
      • [math] \neg{(x \land y)} = \neg{x} \lor \neg{y} [/math]
    2. Далее построим дерево по формуле [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].
    3. Посчитаем какой длины будет [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]
  1. [math] \mathrm{3SAT} \in \mathrm{NP} [/math]
    Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{3SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
  2. [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] на может быть несколько дизъюнктов, которые состоят ровно из трех переменных.
    1. Дизъюнкт содержит не более трех переменных. Тогда возьмем какую-нибудь переменную из этого дизъюнкта и продублируем ее так, чтобы в нем стало ровно 3 переменных. Например: [math] f(y \lor z) = (y \lor z \lor y) [/math], [math] f(y) = (y \lor y \lor y) [/math]
    2. Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: [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]
  1. [math] \mathrm{IND} \in \mathrm{NP} [/math]
    Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{IND} [/math]. Она будет недетерминированно выбирать множество вершин мощности [math] k [/math], проверять, является ли это множество независимым, это можно сделать за полином, и выдавать ответ.
  2. [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].
    1. [math] k [/math] — количество дизъюнктов в [math] x [/math].
    2. Для каждого дизъюнкта создадим по три вершины в графе [math] G [/math], каждая из которой будет сопоставлена переменной из этого дизъюнкта. [math] |V(G)| = 3k [/math]
    3. Соединим вершины из одного дизъюнкта ребрами.
    4. Для всех пар вершин, которые сопоставлены переменным, которые являются отрицаниями друг друга, добавим ребро между этими вершинами.
    Докажем, что [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]

NP-полнота поиска минимального вершинного покрытия в графе

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

[math] \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 [/math]

Лемма:
[math] G [/math] — неориентированный граф. [math] H \subset G [/math] является независимым множеством в [math] G \Rightarrow G \setminus H [/math] является вершинным покрытием в [math] G [/math].
Доказательство:
[math]\triangleright[/math]
  • [math] \Rightarrow [/math]

Пусть [math] H [/math] — независимое множество. Заметим, что по определению независимого множества [math] \forall vu \in E(G) : (v \notin H) \lor (u \notin H) [/math], из чего следует, что [math] (v \in (G \setminus H)) \lor (u \in (G \setminus H)) [/math], это значит, что [math] G \setminus H [/math] — вершинное покрытие.

  • [math] \Leftarrow [/math]
Пусть [math] H [/math] — вершинное покрытие. Заметим, что [math] \forall vu \in E(G) : (v \in H) \lor (u \in H) [/math], из чего следует, что [math] (v \notin (G \setminus H)) \lor (u \notin (G \setminus H)) [/math], это значит, что [math] G \setminus H [/math] — независимое множество.
[math]\triangleleft[/math]
Теорема:
[math] \mathrm{VCOVER} \in \mathrm{NPC} [/math]
Доказательство:
[math]\triangleright[/math]
  1. [math] \mathrm{VCOVER} \in \mathrm{NP} [/math]
    Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{VCOVER} [/math]. Она будет недетерминированно выбирать множество вершин мощности [math] k [/math], проверять, является ли это множество вершинным покрытием, это можно сделать за полином, и выдавать ответ.
  2. [math] \mathrm{VCOVER} \in \mathrm{NPH} [/math]
    Сведем задачу [math] \mathrm{IND} [/math] к задаче [math] \mathrm{VCOVER} [/math]. Построим функцию [math] f(x) [/math], которая будет строить паре [math] \langle G, k \rangle [/math], пару [math] \langle H, l \rangle [/math], такую что [math] x \in \mathrm{IND} \Leftrightarrow f(x) \in \mathrm{VCOVER} [/math], причем [math] |f(x)| \le p(|x|) [/math] для некоторого полинома [math] p [/math].
    [math] f(\langle G, k \rangle) = \langle G, |V(G)| - k \rangle [/math]
    Из доказанной выше леммы, следует, что [math] \langle G, k \rangle \in \mathrm{IND} \Leftrightarrow \langle G, |V(G)| - k \rangle \in \mathrm{VCOVER} [/math]
[math]\triangleleft[/math]


Ссылки