5
правок
Изменения
Нет описания правки
Установим сначала первый факт, то есть <tex>NP</tex>-трудность <tex>3SAT</tex>.
Для этого покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> сводится по Куку к <tex>3SAT</tex>.
Рассмотрим один член булевой формулы в форме КНФ (скобку). В форме 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> к нужному виду.
* <tex>(x \vee y)</tex> заменим на <tex>(x \vee y \vee z) \wedge (x \vee y \vee \neg z)</tex>. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых <tex>z</tex>;
* <tex>(x)</tex> заменим на <tex>(x \vee y) \wedge (x \vee \neg y)</tex> - свели задачу к предыдущей;
