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

Теорема

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

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

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

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

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