Изменения
→Доказательство принадлежности 3SAT классу NPH
===Доказательство принадлежности 3SAT классу NPH===
Покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> [[Сведение_по_Куку|сводится по Куку ]] к <tex>3SAT</tex>.
Рассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид <tex>(x \vee y \vee z)</tex>.
