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