Викиконспекты - Вклад участника [ru]

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

2012-06-16T17:44:26Z

178.178.9.78:

{{В разработке}}

== Введение ==
В этой статье мы рассмотрим класс <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> Нужно доказать, что <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> в унарной системе счисления. Проверим, что <tex> x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>. Пусть <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>. Пусть <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>. Это значит, что <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>. 
# <tex> \mathrm{BH_{1N}} \in \mathrm{NP} </tex> Можно написать недетерминированную программу, которая будет по <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\ \bigm|\ \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
|proof=
# <tex> \mathrm{SAT}\in \mathrm{NP} </tex> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{SAT}\in \mathrm{NPH} </tex> Теперь докажем, что <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>. По определению языка <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> шагов и допускает это слово. В любой момент времени мгновенное описание (МО) <tex>m</tex> есть строка <tex>z\#_qyb</tex>, где <tex>b</tex> — строка, состоящая из такого количества пробелов, чтобы длина всего МО была <tex>t + 1.</tex> Соответственно, начальное МО задаётся так: <tex>\#_sxb</tex>. Если же <tex>|x| > t</tex>, то будем считать, что на ленту записаны лишь первые <tex>t</tex> символов, ведь <tex>m</tex> не может обработать большее количество символов за <tex>t</tex> шагов. Также нам удобно считать, что все вычисления проходят ровно за <tex>t + 1</tex> шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход <tex>q \vdash q</tex>, если в МО <tex>q</tex> есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО <tex>q_t</tex>. Тогда процесс работы машины <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> Общий вид формулы: <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> — образовывать цепочку <tex>x</tex>, а оставшиеся <tex>q_{0,i}</tex> — быть пробелами <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>: <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> принимает значение ''истина''. <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> полиномиально зависит от длины входа — <tex>|\varphi| = O(n^2)</tex>. Покажем, что <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> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{CNFSAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{CNFSAT} \in \mathrm{NPH} </tex> Сведем задачу <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>. Опишем как будет работать функция <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> \mathrm{CNFSAT} \in \mathrm{NP} \land \mathrm{CNFSAT} \in \mathrm{NPH} \Rightarrow \mathrm{CNFSAT} \in \mathrm{NPC} </tex>
}}
=== NP-полнота 3-SAT ===
=== NP-полнота раскраски графа ===
=== NP-полнота поиска минимального вершинного покрытия в графе ===
=== NP-полнота поиска максимальной клики в графе ===
=== NP-полнота поиска гамильтонова цикла и пути в графе ===
=== NP-полнота задачи о рюкзаке ===

== Ссылки ==
* [[Класс P]]
* [[Классы NP и Σ₁]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
[[Категория: Теория сложности]]

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

2012-06-16T16:03:53Z

178.178.9.78:

{{В разработке}}

== Введение ==
В этой статье мы рассмотрим класс <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> Нужно доказать, что <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> в унарной системе счисления. Проверим, что <tex> x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>. Пусть <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>. Пусть <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>. Это значит, что <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>. 
# <tex> \mathrm{BH_{1N}} \in \mathrm{NP} </tex> Можно написать недетерминированную программу, которая будет по <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\ \bigm|\ \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
|proof=
# <tex> \mathrm{SAT}\in \mathrm{NP} </tex> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{SAT}\in \mathrm{NPH} </tex> Теперь докажем, что <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>. По определению языка <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> шагов и допускает это слово. В любой момент времени мгновенное описание (МО) <tex>m</tex> есть строка <tex>z\#_qyb</tex>, где <tex>b</tex> — строка, состоящая из такого количества пробелов, чтобы длина всего МО была <tex>t + 1.</tex> Соответственно, начальное МО задаётся так: <tex>\#_sxb</tex>. Если же <tex>|x| > t</tex>, то будем считать, что на ленту записаны лишь первые <tex>t</tex> символов, ведь <tex>m</tex> не может обработать большее количество символов за <tex>t</tex> шагов. Также нам удобно считать, что все вычисления проходят ровно за <tex>t + 1</tex> шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход <tex>q \vdash q</tex>, если в МО <tex>q</tex> есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО <tex>q_t</tex>. Тогда процесс работы машины <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> Общий вид формулы: <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> — образовывать цепочку <tex>x</tex>, а оставшиеся <tex>q_{0,i}</tex> — быть пробелами <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>: <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> принимает значение ''истина''. <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> полиномиально зависит от длины входа — <tex>|\varphi| = O(n^2)</tex>. Покажем, что <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> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{CNFSAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# Сведем задачу <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>. Опишем как будет работать функция <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>.
}}
=== NP-полнота 3-SAT ===
=== NP-полнота раскраски графа ===
=== NP-полнота поиска минимального вершинного покрытия в графе ===
=== NP-полнота поиска максимальной клики в графе ===
=== NP-полнота поиска гамильтонова цикла и пути в графе ===
=== NP-полнота задачи о рюкзаке ===

== Ссылки ==
* [[Класс P]]
* [[Классы NP и Σ₁]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
[[Категория: Теория сложности]]