202
правки
Изменения
Нет описания правки
== Теорема ==
<tex> CNFSAT \in NPC. </tex>, то есть задача [[NP-полнота|NP-полная]].
== Доказательство ==
Для доказательства теоремы необходимо установить два факта:
* <tex> CNFSAT \in NPH </tex>
==== Доказательство принадлежности классу NP ====
В качестве сертификата выберем множество <tex> \{y_1, ...,y_n\} </tex>, представляющее собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу <tex> \phi(x_1, ..., x_n) </tex> и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности. Таким образом, <tex> CNFSAT \in \Sigma_1 = NP </tex>
==== Доказательство принадлежности классу NPH ====
* Второй этап - переписать формулу, которая представляет собой логическое '''И''' и '''ИЛИ''' литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы. Рассмотрим дерево разбора произвольной формулы. Листья этого дерева будут соответствовать литералам, а узлы - логической операции '''И''' или '''ИЛИ''' над двумя его потомками.
# Для узла с меткой '''И''' соответствующая КНФ получается как конъюнкция ('''И''') всех дизъюнктов двух подформул <tex> \alpha </tex> и <tex> \beta </tex>, уже находящихся в КНФ.# Для узла с меткой '''ИЛИ''' нужно ввести новую переменную. Добавляем ее во все дизъюнкты левого операнда <tex> \alpha </tex> и ее отрицание во все дизъюнкты правого операнда <tex> \beta </tex>. Можно заметитьЗаметим, что формула <tex> \alpha \vee \beta </tex> выполнима тогда и только тогда, когда выполнима <tex> (\alpha \vee y) \wedge (\beta \vee \neg y) , </tex>, где <tex> y </tex> - новая переменная.После чего, воспользовавшись законами преобразования в каждой формуле в скобках, получим формулы в КНФ: <tex> \alpha \vee y = ((...)\wedge(...)\wedge ... \wedge(...)) \vee y = (...\vee y)\wedge(...\vee y)\wedge...\wedge(...\vee y). </tex> Аналогично преобразуем <tex> \beta \vee \neg y </tex>.Каждый раз новая формула увеличивается не более, чем на количество листьев в поддереве, а значит максимальный размер формулы <tex> \omega </tex> можно представить как ''(число листьев) * (число вершин)'', что соответствует оценке работы алгоритма <tex> O(|\phi|^2) </tex>. Таким образом, условия сведения выполнены, и действительно <tex> CNFSAT \in NPH </tex>. Теорема доказана. [[Категория:NP]]
