Изменения
→Доказательство принадлежности 3SAT классу NPH
* <tex>(x \vee y)</tex> заменим на <tex>(x \vee y \vee z) \wedge (x \vee y \vee \neg z)</tex>. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых <tex>z</tex>;
* <tex>(x)</tex> заменим на <tex>(x \vee y) \wedge (x \vee \neg y)</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>(x_{1}^* \ldots x_{k}^*)</tex> - набор значений <tex>x_i</tex>, удовлетворяющий дизъюнкт <tex>(x_1 \ldots x_k)</tex>, то существует набор значений <tex>z_i</tex> - <tex>z_{1}^* \ldots z_{k-3}^*</tex>, что каждый из <tex>k-2</tex>-х новых дизъюнктов также удовлетворен.
Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана.
