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