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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
{{В разработке}}
 
  
 
== Введение ==
 
== Введение ==
Строка 30: Строка 29:
 
|proof=
 
|proof=
 
# <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>, у нас есть недетерминированная машина Тьюринга <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> может быть представлен следующей таблицей :  
+
# <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">
 
<table align="right" border="1" style="text-align:center" cellspacing="0">
 
<tr>  
 
<tr>  
Строка 259: Строка 262:
 
== Другие примеры NP-полных языков ==
 
== Другие примеры NP-полных языков ==
 
=== NP-полнота CNFSAT ===
 
=== NP-полнота CNFSAT ===
<tex> \mathrm{CNFSAT} </tex>{{---}} язык булевых формул, заданных в [[КНФ]], таких что для них существует подстановка, при которой формула истинна.  
+
<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>
 
<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>
Строка 280: Строка 283:
 
}}
 
}}
 
=== NP-полнота 3-SAT ===
 
=== NP-полнота 3-SAT ===
<tex> \mathrm{3SAT} </tex>{{---}} язык булевых формул, заданных в [[КНФ]], таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна.  
+
<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>
 
<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>
Строка 295: Строка 298:
 
}}
 
}}
 
=== NP-полнота поиска максимального независимого множества ===
 
=== NP-полнота поиска максимального независимого множества ===
<tex> \mathrm{IND} </tex>{{---}} язык неориентированных графов, таких что в графе есть независимое множество величины <tex> k </tex>.
+
<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>
 
<tex> \mathrm{IND} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) </tex>, такое что <tex> H </tex> независимо в <tex> G \rbrace </tex>
Строка 314: Строка 317:
 
}}
 
}}
 
=== 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>
 +
}}
 +
 
  
 
== Ссылки ==
 
== Ссылки ==

Текущая версия на 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]


Ссылки