NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Версия от 23:07, 15 марта 2010; Chivilikhin.daniil (обсуждение | вклад)
Теорема
, т.е. задача о выполнимости булевой формулы в форме 3-КНФ -полна.
Доказательство
Для того, чтобы доказать
-полноту задачи, необходимо установить следующие факты:- ;
- .
Установим сначала первый факт, то есть
-трудность . Для этого покажем, что , то есть сводится по Куку к .