NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Версия от 14:43, 19 марта 2010; 192.168.0.2 (обсуждение) (→Доказательство принадлежности 3SAT классу NPH)
Содержание
Задача
в 3-КНФ,
Теорема
Доказательство
Для того, чтобы доказать NP-полноту задачи, необходимо установить следующие факты:
- .
- ;
Доказательство принадлежности 3SAT классу NP
Возьмем в качестве сертификата набор
, где . Верификатор подставляет в формулу и проверяет её на равенство единице. Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, .Доказательство принадлежности 3SAT классу NPH
Покажем, что сводится по Куку к .
, то естьРассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид . Научимся приводить члены вида , , к нужному виду.
- заменим на . Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых ;
- заменим на - свели задачу к предыдущей;
- Если встречается дизъюнкт вида , введем новых переменных и заменим наш дизъюнкт на дизъюнкта: . Покажем, что эта замена корректна.
Для этого, сделаем несколько утверждений:
- Если - набор значений , удовлетворяющий дизъюнкт , то существует набор значений , что каждый из -х новых дизъюнктов также удовлетворен.
Таким образом, мы свели
к , следовательно . Теорема доказана.