14
правок
Изменения
→Доказательство принадлежности классу NPH
# <tex> \neg(x \vee y) = \neg x \wedge \neg y </tex>
# <tex> \neg(\neg x) = x </tex>
* Второй этап - переписать формулу, которая представляет собой логическое '''И''' и '''ИЛИ''' литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы.
