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