Изменения
→Доказательство принадлежности 3SAT классу NPH
Для этого, сделаем несколько утверждений:
* Если <tex>(x_{1}^* \ldots x_{k}^*)</tex> - набор значений <tex>x_i</tex>, удовлетворяющий дизъюнкт <tex>(x_1 \vee \ldots \vee 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>. Теорема доказана.
