NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Версия от 17:35, 16 марта 2010; 192.168.0.2 (обсуждение)
Теорема
, т.е. задача о выполнимости булевой формулы в форме 3-КНФ -полна.
Доказательство
Для того, чтобы доказать
-полноту задачи, необходимо установить следующие факты:- .
- ;
Для того, чтобы доказать первый факт, предъявим сертификат: набор , удовлетворяющий формулу.
Теперь докажем
-трудность . Для этого покажем, что , то есть сводится по Куку к .Рассмотрим один член булевой формулы в форме КНФ (скобку). В форме 3-КНФ этот член должен иметь вид
. Научимся приводить члены вида , , к нужному виду.- заменим на . Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых ;
- заменим на - свели задачу к предыдущей;
- Если встречается скобка вида , введем новых переменных и заменим нашу скобку на скобки: