Изменения

Для этого, сделаем два утверждения:

# Если <tex>(x_{1}^* \ldots x_{k}^*)</tex> - набор значений <tex>x_i</tex>, удовлетворяющий дизъюнкт <tex>(x_1 \vee \ldots \vee x_k)</tex>, то существует такой набор значений <tex>z_{1}^* \ldots z_{k-3}^*</tex>, что каждый из <tex>k-2</tex> новых дизъюнктов также удовлетворен.

Предположим, что это не так, и <tex>x_i = false, i = 1..k</tex>. Тогда, первые <tex>k-3</tex> дизъюнкта в <tex>3SAT</tex> удовлетворены только если <tex>z_i = true, i=1..k-3</tex>. Однако, если <tex>z_{k-3}=true</tex>, то последний дизъюнкт <tex>(x_{k-1} \vee x_k \vee \neg z_{k-3})</tex> не может быть удовлетворен. Пришли к противоречию, следовательно хотя бы один из <tex>x_i</tex> должен равняться <tex>true</tex>.

Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана.