Изменения

## Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: <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>.