Примеры 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]

[math] \mathrm{CNFSAT} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{CNFSAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ. [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]. Для начала преобразуем формулу так, чтобы все отрицания относились только к переменным. Это можно сделать по правилам: [math] \neg{(x \lor y)} = \neg{x} \land \neg{y} [/math] [math] \neg{(x \land y)} = \neg{x} \lor \neg{y} [/math] Далее построим дерево по формуле [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]. Посчитаем какой длины будет [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]

[math] \mathrm{3SAT} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{3SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ. [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] на может быть несколько дизъюнктов, которые состоят ровно из трех переменных. Дизъюнкт содержит не более трех переменных. Тогда возьмем какую-нибудь переменную из этого дизъюнкта и продублируем ее так, чтобы в нем стало ровно 3 переменных. Например: [math] f(y \lor z) = (y \lor z \lor y) [/math], [math] f(y) = (y \lor y \lor y) [/math] Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: [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]

[math] \mathrm{IND} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{IND} [/math]. Она будет недетерминированно выбирать множество вершин мощности [math] k [/math], проверять, является ли это множество независимым, это можно сделать за полином, и выдавать ответ. [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]. [math] k [/math] — количество дизъюнктов в [math] x [/math]. Для каждого дизъюнкта создадим по три вершины в графе [math] G [/math], каждая из которой будет сопоставлена переменной из этого дизъюнкта. [math] |V(G)| = 3k [/math] Соединим вершины из одного дизъюнкта ребрами. Для всех пар вершин, которые сопоставлены переменным, которые являются отрицаниями друг друга, добавим ребро между этими вершинами. Докажем, что [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]

[math] \mathrm{VCOVER} \in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{VCOVER} [/math]. Она будет недетерминированно выбирать множество вершин мощности [math] k [/math], проверять, является ли это множество вершинным покрытием, это можно сделать за полином, и выдавать ответ. [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]

См. также

• Класс P
• Классы NP и Σ₁
• NP-полнота BH1N
• Теорема Кука
• Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
• Список NP-полных задач