Изменения
→Доказательство принадлежности 3SAT классу NPH
Докажем эти утверждения. Пусть все новые дизъюнкты удовлетворяются некоторым набором значений <tex>x_i</tex> и <tex>z_i</tex>. Покажем, что тогда хотя бы один из <tex>x_i</tex> должен равняться <tex>true</tex>.
Предположим, что это не так, и <tex>x_i = false, \foreach i = 1..k</tex>
Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана.
