Изменения
Нет описания правки
Для того, чтобы доказать первый факт, предъявим сертификат: набор <tex>x_1 \ldots x_{n}</tex>, удовлетворяющий формулу. Итак, <tex>SAT \in NP</tex>.
Теперь докажем <tex>NP</tex>-трудность <tex>3SAT</tex>.
* Если встречается скобка вида <tex>(x_1 \ldots x_k), k \ge 3</tex>, введем <tex>k-3</tex> новых переменных и заменим нашу скобку на <tex>k-2</tex> скобки: <tex>(x_1 \vee x_2 \vee z_1) \wedge (x_3 \vee \neg z_1 \vee z_2) \wedge (x_4 \vee \neg z_2 \vee z_3) \wedge \ldots \wedge (x_{k-1} \vee x_k \vee \neg z_{k-3})</tex>
Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>SAT 3SAT \in NPH</tex>. Теорема доказана.
