Изменения
Новая страница: «== NP-полнота CNFSAT == <tex> \mathrm{CNFSAT} </tex> {{---}} язык булевых формул, заданных в КНФ, таких что для...»
== NP-полнота CNFSAT ==
<tex> \mathrm{CNFSAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что для них существует подстановка, при которой формула истинна.
<tex> \mathrm{CNFSAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi </tex> задано в КНФ и <tex> \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace </tex>
{{Теорема
|statement= <tex> \mathrm{CNFSAT} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{CNFSAT} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{CNFSAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{CNFSAT} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{SAT} </tex> к задаче <tex> \mathrm{CNFSAT} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле, булевую формулу в [[КНФ]], такую что <tex> x \in \mathrm{SAT} \Leftrightarrow f(x) \in \mathrm{CNFSAT} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>.
##Для начала преобразуем формулу так, чтобы все отрицания относились только к переменным. Это можно сделать по правилам:
##* <tex> \neg{(x \lor y)} = \neg{x} \land \neg{y} </tex>
##* <tex> \neg{(x \land y)} = \neg{x} \lor \neg{y} </tex>
## Далее построим дерево по формуле <tex> x </tex>. Будем строить формулу в [[КНФ]] для поддеревьев рекурсивно. Есть два случая:
##* Корень дерева {{---}} <tex> \land </tex>. Пусть левое и правое поддерево <tex> x </tex> {{---}} это <tex> x_l </tex> и <tex> x_r </tex> соответственно. Тогда <tex> f(x) = f(x_l) \land f(x_r) </tex>.
##* Корень дерева {{---}} <tex> \lor </tex>. Пусть левое и правое поддерево <tex> x </tex> {{---}} это <tex> x_l </tex> и <tex> x_r </tex> соответственно. Создадим новую переменную <tex> z </tex>. Тогда <tex> f(x) = (f(x_l) \lor z) \land (f(x_r) \lor \neg{z}) </tex>. <tex> f(x_l) </tex> и <tex> f(x_r) </tex> {{---}} формулы в [[КНФ]], поэтому переменную <tex> z </tex> и ее отрицание можно внести в каждую скобку в <tex> f(x_l) </tex> и <tex> f(x_r) </tex>.
## Посчитаем какой длины будет <tex> f(x) </tex>. Это зависит от количества логических операций в формуле. Заметим, что количество скобок в конечной формуле равно количеству операций <tex> \land </tex>. Количество операций <tex> \land </tex> не более чем <tex> |x| </tex>, так как <tex> \land </tex> добавляется один раз в первом из рассмотренных выше случаев. А во втором из рассмотренных случаев добавляется <tex> \lor </tex> в том количестве, сколько скобок у нас есть. А количество скобок равно количеству <tex> \land </tex>, поэтому количество операций <tex> \lor </tex> не превысит <tex> |x|^2 </tex>. Поэтому <tex> f </tex> будет работать за полином.
:Значит <tex> \mathrm{CNFSAT} \in \mathrm{NPC} </tex>.
}}
== NP-полнота 3-SAT ==
<tex> \mathrm{3SAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна.
<tex> \mathrm{3SAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi </tex> задано в 3КНФ и <tex> \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace </tex>
{{Теорема
|statement= <tex> \mathrm{3SAT} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{3SAT} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{3SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{3SAT} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{CNFSAT} </tex> к задаче <tex> \mathrm{3SAT} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле в [[КНФ]], булевую формулу в 3-КНФ, такую что <tex> x \in \mathrm{CNFSAT} \Leftrightarrow f(x) \in \mathrm{3SAT} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>. <br> Заменим каждый дизъюнкт в <tex> x </tex> на может быть несколько дизъюнктов, которые состоят ровно из трех переменных.
## Дизъюнкт содержит не более трех переменных. Тогда возьмем какую-нибудь переменную из этого дизъюнкта и продублируем ее так, чтобы в нем стало ровно 3 переменных. Например: <tex> f(y \lor z) = (y \lor z \lor y) </tex>, <tex> f(y) = (y \lor y \lor y) </tex>
## Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: <tex> (x_1 \lor x_2 \lor \ldots \lor x_k) </tex>, создадим новые переменные <tex> z_1, z_2, \ldots, z_{k - 2} </tex>, и тогда <br> <tex> f(x_1 \lor x_2 \lor \ldots \lor x_k) = (x_1~\lor~x_2~\lor~z_1)~\land~(x_3~\lor~\neg{z_1}~\lor~z_2)~\land~\ldots~\land~(x_i~\lor~\neg{z_{i - 2}}~\lor~z_{i - 1})~\land~\ldots~\land~(x_{k - 1}~\lor~x_k~\lor~\neg{z_{k - 2}}) </tex> <br> Можно заметить, что если какое-то <tex> x_i = 1 </tex>, то существует подстановка для <tex> z_1, z_2, \ldots, z_{k - 1} </tex>, такая что <tex> f(x_1 \lor x_2 \lor \ldots \lor x_k)</tex> удовлетворима. Также, если <tex> \forall i : x_i = 0 </tex>, нельзя удовлетворить все скобки, так как каждая скобка удовлетворяется только переменными <tex> z_1, z_2, \ldots, z_{k - 2} </tex>, можно понять, что при выборе значения <tex> z_1 </tex> все переменные восстанавливаются однозначно и значение <tex> z_{k - 2} </tex> нельзя выбрать так, чтобы удовлетворить последние две скобки одновременно. А значит <tex> x \in CNFSAT \Leftrightarrow f(x) \in 3SAT </tex>.
#:Заметим, что размер формулы возрос не более чем в три раза, поэтому функция <tex> f </tex> будет работать за полином.
:Значит <tex> \mathrm{3SAT} \in \mathrm{NPC} </tex>
}}
== NP-полнота поиска максимального независимого множества ==
<tex> \mathrm{IND} </tex> {{---}} язык неориентированных графов, таких что в графе есть независимое множество мощности <tex> k </tex>.
<tex> \mathrm{IND} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) </tex>, такое что <tex> H </tex> независимо в <tex> G \rbrace </tex>
{{Теорема
|statement= <tex> \mathrm{IND} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{IND} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{IND} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество независимым, это можно сделать за полином, и выдавать ответ.
# <tex> \mathrm{IND} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{3SAT} </tex> к задаче <tex> \mathrm{IND} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле в 3-КНФ, пару <tex> \langle G, k \rangle </tex>, такую что <tex> x \in \mathrm{3SAT} \Leftrightarrow f(x) \in \mathrm{IND} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>.
## <tex> k </tex> {{---}} количество дизъюнктов в <tex> x </tex>.
## Для каждого дизъюнкта создадим по три вершины в графе <tex> G </tex>, каждая из которой будет сопоставлена переменной из этого дизъюнкта. <tex> |V(G)| = 3k </tex>
## Соединим вершины из одного дизъюнкта ребрами.
## Для всех пар вершин, которые сопоставлены переменным, которые являются отрицаниями друг друга, добавим ребро между этими вершинами.
#: Докажем, что <tex> x \in \mathrm{3SAT} \Leftrightarrow \langle G, k \rangle \in \mathrm{IND} </tex>
#* Пусть формула <tex> x </tex> удовлетворима. Тогда в каждом дизъюнкте будет будет существовать вершина, что сопоставленная ей переменная истинна. Для каждого дизъюнкта выберем ровно одну такую вершину. Это множество будет мощности <tex> k </tex> и независимым, потому что в каждом дизъюнкте мы выбрали ровно одну переменную и мы не выбрали пару вершин, которые сопоставленны переменным, которые являются отрицаниями друг друга.
#* Пусть существует независимое множество мощности <tex> k </tex> в графе <tex> G </tex>. Тогда известно, что для каждого дизъюнкта не может быть выбрано более одной вершины из нее, значит из каждого дизъюнкта выбрана ровно одна вершина, потому что всего вершин {{---}} <tex> k </tex>. Теперь если мы удовлетворим каждую переменную, сопоставленная вершина которой в независимом множестве, вся формула удовлетворится. А каждую переменную можно удовлетворить, потому что в независимом множестве нет пары вершин, которым сопоставлены переменные, которые являются отрицаниями друг друга. Значит формула удовлетворима.
: А значит <tex> \mathrm{IND} \in \mathrm{NPC} </tex>.
}}
== NP-полнота поиска минимального вершинного покрытия в графе ==
<tex> \mathrm{VCOVER} </tex> {{---}} язык неориентированных графов, таких что в графе есть вершинное покрытие мощности <tex> k </tex>.
<tex> \mathrm{VCOVER} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) : \forall vu \in E(G), (v \in H) \lor (u \in H) \rbrace </tex>
{{Лемма
|statement = <tex> G </tex> {{---}} неориентированный граф. <tex> H \subset G </tex> является независимым множеством в <tex> G \Rightarrow G \setminus H </tex> является вершинным покрытием в <tex> G </tex>.
|proof=
* <tex> \Rightarrow </tex>
Пусть <tex> H </tex> {{---}} независимое множество. Заметим, что по определению независимого множества <tex> \forall vu \in E(G) : (v \notin H) \lor (u \notin H) </tex>, из чего следует, что <tex> (v \in (G \setminus H)) \lor (u \in (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} вершинное покрытие.
* <tex> \Leftarrow </tex>
Пусть <tex> H </tex> {{---}} вершинное покрытие. Заметим, что <tex> \forall vu \in E(G) : (v \in H) \lor (u \in H) </tex>, из чего следует, что <tex> (v \notin (G \setminus H)) \lor (u \notin (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} независимое множество.
}}
{{Теорема
|statement= <tex> \mathrm{VCOVER} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{VCOVER} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{VCOVER} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество вершинным покрытием, это можно сделать за полином, и выдавать ответ.
# <tex> \mathrm{VCOVER} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{IND} </tex> к задаче <tex> \mathrm{VCOVER} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить паре <tex> \langle G, k \rangle </tex>, пару <tex> \langle H, l \rangle </tex>, такую что <tex> x \in \mathrm{IND} \Leftrightarrow f(x) \in \mathrm{VCOVER} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> <tex> f(\langle G, k \rangle) = \langle G, |V(G)| - k \rangle </tex> <br> Из доказанной выше леммы, следует, что <tex> \langle G, k \rangle \in \mathrm{IND} \Leftrightarrow \langle G, |V(G)| - k \rangle \in \mathrm{VCOVER} </tex>
}}
== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]
* [[NP-полнота BH1N]]
* [[Теорема Кука]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
* [http://en.wikipedia.org/wiki/List_of_NP-complete_problems Список NP-полных задач]
[[Категория: Теория сложности]]
<tex> \mathrm{CNFSAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что для них существует подстановка, при которой формула истинна.
<tex> \mathrm{CNFSAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi </tex> задано в КНФ и <tex> \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace </tex>
{{Теорема
|statement= <tex> \mathrm{CNFSAT} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{CNFSAT} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{CNFSAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{CNFSAT} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{SAT} </tex> к задаче <tex> \mathrm{CNFSAT} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле, булевую формулу в [[КНФ]], такую что <tex> x \in \mathrm{SAT} \Leftrightarrow f(x) \in \mathrm{CNFSAT} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>.
##Для начала преобразуем формулу так, чтобы все отрицания относились только к переменным. Это можно сделать по правилам:
##* <tex> \neg{(x \lor y)} = \neg{x} \land \neg{y} </tex>
##* <tex> \neg{(x \land y)} = \neg{x} \lor \neg{y} </tex>
## Далее построим дерево по формуле <tex> x </tex>. Будем строить формулу в [[КНФ]] для поддеревьев рекурсивно. Есть два случая:
##* Корень дерева {{---}} <tex> \land </tex>. Пусть левое и правое поддерево <tex> x </tex> {{---}} это <tex> x_l </tex> и <tex> x_r </tex> соответственно. Тогда <tex> f(x) = f(x_l) \land f(x_r) </tex>.
##* Корень дерева {{---}} <tex> \lor </tex>. Пусть левое и правое поддерево <tex> x </tex> {{---}} это <tex> x_l </tex> и <tex> x_r </tex> соответственно. Создадим новую переменную <tex> z </tex>. Тогда <tex> f(x) = (f(x_l) \lor z) \land (f(x_r) \lor \neg{z}) </tex>. <tex> f(x_l) </tex> и <tex> f(x_r) </tex> {{---}} формулы в [[КНФ]], поэтому переменную <tex> z </tex> и ее отрицание можно внести в каждую скобку в <tex> f(x_l) </tex> и <tex> f(x_r) </tex>.
## Посчитаем какой длины будет <tex> f(x) </tex>. Это зависит от количества логических операций в формуле. Заметим, что количество скобок в конечной формуле равно количеству операций <tex> \land </tex>. Количество операций <tex> \land </tex> не более чем <tex> |x| </tex>, так как <tex> \land </tex> добавляется один раз в первом из рассмотренных выше случаев. А во втором из рассмотренных случаев добавляется <tex> \lor </tex> в том количестве, сколько скобок у нас есть. А количество скобок равно количеству <tex> \land </tex>, поэтому количество операций <tex> \lor </tex> не превысит <tex> |x|^2 </tex>. Поэтому <tex> f </tex> будет работать за полином.
:Значит <tex> \mathrm{CNFSAT} \in \mathrm{NPC} </tex>.
}}
== NP-полнота 3-SAT ==
<tex> \mathrm{3SAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна.
<tex> \mathrm{3SAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi </tex> задано в 3КНФ и <tex> \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace </tex>
{{Теорема
|statement= <tex> \mathrm{3SAT} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{3SAT} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{3SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.
# <tex> \mathrm{3SAT} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{CNFSAT} </tex> к задаче <tex> \mathrm{3SAT} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле в [[КНФ]], булевую формулу в 3-КНФ, такую что <tex> x \in \mathrm{CNFSAT} \Leftrightarrow f(x) \in \mathrm{3SAT} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>. <br> Заменим каждый дизъюнкт в <tex> x </tex> на может быть несколько дизъюнктов, которые состоят ровно из трех переменных.
## Дизъюнкт содержит не более трех переменных. Тогда возьмем какую-нибудь переменную из этого дизъюнкта и продублируем ее так, чтобы в нем стало ровно 3 переменных. Например: <tex> f(y \lor z) = (y \lor z \lor y) </tex>, <tex> f(y) = (y \lor y \lor y) </tex>
## Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: <tex> (x_1 \lor x_2 \lor \ldots \lor x_k) </tex>, создадим новые переменные <tex> z_1, z_2, \ldots, z_{k - 2} </tex>, и тогда <br> <tex> f(x_1 \lor x_2 \lor \ldots \lor x_k) = (x_1~\lor~x_2~\lor~z_1)~\land~(x_3~\lor~\neg{z_1}~\lor~z_2)~\land~\ldots~\land~(x_i~\lor~\neg{z_{i - 2}}~\lor~z_{i - 1})~\land~\ldots~\land~(x_{k - 1}~\lor~x_k~\lor~\neg{z_{k - 2}}) </tex> <br> Можно заметить, что если какое-то <tex> x_i = 1 </tex>, то существует подстановка для <tex> z_1, z_2, \ldots, z_{k - 1} </tex>, такая что <tex> f(x_1 \lor x_2 \lor \ldots \lor x_k)</tex> удовлетворима. Также, если <tex> \forall i : x_i = 0 </tex>, нельзя удовлетворить все скобки, так как каждая скобка удовлетворяется только переменными <tex> z_1, z_2, \ldots, z_{k - 2} </tex>, можно понять, что при выборе значения <tex> z_1 </tex> все переменные восстанавливаются однозначно и значение <tex> z_{k - 2} </tex> нельзя выбрать так, чтобы удовлетворить последние две скобки одновременно. А значит <tex> x \in CNFSAT \Leftrightarrow f(x) \in 3SAT </tex>.
#:Заметим, что размер формулы возрос не более чем в три раза, поэтому функция <tex> f </tex> будет работать за полином.
:Значит <tex> \mathrm{3SAT} \in \mathrm{NPC} </tex>
}}
== NP-полнота поиска максимального независимого множества ==
<tex> \mathrm{IND} </tex> {{---}} язык неориентированных графов, таких что в графе есть независимое множество мощности <tex> k </tex>.
<tex> \mathrm{IND} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) </tex>, такое что <tex> H </tex> независимо в <tex> G \rbrace </tex>
{{Теорема
|statement= <tex> \mathrm{IND} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{IND} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{IND} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество независимым, это можно сделать за полином, и выдавать ответ.
# <tex> \mathrm{IND} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{3SAT} </tex> к задаче <tex> \mathrm{IND} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле в 3-КНФ, пару <tex> \langle G, k \rangle </tex>, такую что <tex> x \in \mathrm{3SAT} \Leftrightarrow f(x) \in \mathrm{IND} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>.
## <tex> k </tex> {{---}} количество дизъюнктов в <tex> x </tex>.
## Для каждого дизъюнкта создадим по три вершины в графе <tex> G </tex>, каждая из которой будет сопоставлена переменной из этого дизъюнкта. <tex> |V(G)| = 3k </tex>
## Соединим вершины из одного дизъюнкта ребрами.
## Для всех пар вершин, которые сопоставлены переменным, которые являются отрицаниями друг друга, добавим ребро между этими вершинами.
#: Докажем, что <tex> x \in \mathrm{3SAT} \Leftrightarrow \langle G, k \rangle \in \mathrm{IND} </tex>
#* Пусть формула <tex> x </tex> удовлетворима. Тогда в каждом дизъюнкте будет будет существовать вершина, что сопоставленная ей переменная истинна. Для каждого дизъюнкта выберем ровно одну такую вершину. Это множество будет мощности <tex> k </tex> и независимым, потому что в каждом дизъюнкте мы выбрали ровно одну переменную и мы не выбрали пару вершин, которые сопоставленны переменным, которые являются отрицаниями друг друга.
#* Пусть существует независимое множество мощности <tex> k </tex> в графе <tex> G </tex>. Тогда известно, что для каждого дизъюнкта не может быть выбрано более одной вершины из нее, значит из каждого дизъюнкта выбрана ровно одна вершина, потому что всего вершин {{---}} <tex> k </tex>. Теперь если мы удовлетворим каждую переменную, сопоставленная вершина которой в независимом множестве, вся формула удовлетворится. А каждую переменную можно удовлетворить, потому что в независимом множестве нет пары вершин, которым сопоставлены переменные, которые являются отрицаниями друг друга. Значит формула удовлетворима.
: А значит <tex> \mathrm{IND} \in \mathrm{NPC} </tex>.
}}
== NP-полнота поиска минимального вершинного покрытия в графе ==
<tex> \mathrm{VCOVER} </tex> {{---}} язык неориентированных графов, таких что в графе есть вершинное покрытие мощности <tex> k </tex>.
<tex> \mathrm{VCOVER} = \lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) : \forall vu \in E(G), (v \in H) \lor (u \in H) \rbrace </tex>
{{Лемма
|statement = <tex> G </tex> {{---}} неориентированный граф. <tex> H \subset G </tex> является независимым множеством в <tex> G \Rightarrow G \setminus H </tex> является вершинным покрытием в <tex> G </tex>.
|proof=
* <tex> \Rightarrow </tex>
Пусть <tex> H </tex> {{---}} независимое множество. Заметим, что по определению независимого множества <tex> \forall vu \in E(G) : (v \notin H) \lor (u \notin H) </tex>, из чего следует, что <tex> (v \in (G \setminus H)) \lor (u \in (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} вершинное покрытие.
* <tex> \Leftarrow </tex>
Пусть <tex> H </tex> {{---}} вершинное покрытие. Заметим, что <tex> \forall vu \in E(G) : (v \in H) \lor (u \in H) </tex>, из чего следует, что <tex> (v \notin (G \setminus H)) \lor (u \notin (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} независимое множество.
}}
{{Теорема
|statement= <tex> \mathrm{VCOVER} \in \mathrm{NPC} </tex>
|proof=
#<tex> \mathrm{VCOVER} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{VCOVER} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество вершинным покрытием, это можно сделать за полином, и выдавать ответ.
# <tex> \mathrm{VCOVER} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{IND} </tex> к задаче <tex> \mathrm{VCOVER} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить паре <tex> \langle G, k \rangle </tex>, пару <tex> \langle H, l \rangle </tex>, такую что <tex> x \in \mathrm{IND} \Leftrightarrow f(x) \in \mathrm{VCOVER} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> <tex> f(\langle G, k \rangle) = \langle G, |V(G)| - k \rangle </tex> <br> Из доказанной выше леммы, следует, что <tex> \langle G, k \rangle \in \mathrm{IND} \Leftrightarrow \langle G, |V(G)| - k \rangle \in \mathrm{VCOVER} </tex>
}}
== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]
* [[NP-полнота BH1N]]
* [[Теорема Кука]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
* [http://en.wikipedia.org/wiki/List_of_NP-complete_problems Список NP-полных задач]
[[Категория: Теория сложности]]
