NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ

Теорема

[math]3SAT \in NPC [/math], т.е. задача о выполнимости булевой формулы в форме 3-КНФ [math]NP[/math]-полна.

Доказательство

Для того, чтобы доказать [math]NP[/math]-полноту задачи, необходимо установить следующие факты:

1. [math] 3SAT \in NP [/math].
2. [math] 3SAT \in NPH [/math];

Для того, чтобы доказать первый факт, предъявим сертификат: набор [math]x_1 \ldots x_{n}[/math], удовлетворяющий формулу.

Теперь докажем [math]NP[/math]-трудность [math]3SAT[/math]. Для этого покажем, что [math]CNFSAT \le 3SAT[/math], то есть [math]CNFSAT[/math] сводится по Куку к [math]3SAT[/math].

Рассмотрим один член булевой формулы в форме КНФ (скобку). В форме 3-КНФ этот член должен иметь вид [math](x \vee y \vee z)[/math]. Научимся приводить члены вида [math](x)[/math], [math](x \vee y)[/math], [math](x_1 \vee x_{2} \vee \ldots \vee x_{m})[/math] к нужному виду.

• [math](x \vee y)[/math] заменим на [math](x \vee y \vee z) \wedge (x \vee y \vee \neg z)[/math]. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых [math]z[/math];
• [math](x)[/math] заменим на [math](x \vee y) \wedge (x \vee \neg y)[/math] - свели задачу к предыдущей;
• Если встречается скобка вида [math](x_1 \ldots x_k), k \ge 3[/math], введем [math]k-3[/math] новых переменных и заменим нашу скобку на [math]k-2[/math] скобки: [math](x_1 \vee x_2 \vee z_1) \wedge (x_3 \vee \neg z_1 \vee z_2) \wedge (x_4 \vee \neg z_2 \vee z_3) \wedge \ldots \wedge (x_{k-1} \vee x_k \vee \neg z_{k-3})[/math]