NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Версия от 14:12, 19 марта 2010; AntonSafronov (обсуждение | вклад) (→Доказательство принадлежности классу NPH)
Содержание
Определения
- Литералом является переменная или отрицание переменной. Например, или .
- Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например,
- Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.
Определение
SAT — задача о выполнимости булевой формулы в форме КНФ.
в КНФ,Теорема
Доказательство
Для доказательства теоремы необходимо установить два факта:
Доказательство принадлежности классу NP
В качестве сертификата выберем множество
, представляющее собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности. Таким образом,Доказательство принадлежности классу NPH
Выполним сведение по Карпу задачи
к задаче . Для этого необходимо построить функцию , вычислимую за полиномиальное время от длины входа, которая выполняла бы преобразование , где в КНФ. Заметим, что в общем случае время построения эквивалентной формулы в форме КНФ может оказаться больше полиномиального. В частности, длина формулы может вырасти экспоненциально, и тогда время порождения тоже экспоненциально вырастет. Однако нам достаточно предъявить формулу , которая будет выполнима тогда и только тогда, когда выполнима исходная формула . При этом формулы могут оказаться не эквивалентными, ввиду, например, добавления новых переменных.Итак, опишем действия функции
.- На первом этапе все отрицания спускаются вниз по дереву выражения, так что в формуле остаются только отрицания переменных. Булева формула превращается в логические И и ИЛИ литералов. Это преобразование дает формулу, эквивалентную исходной, и занимает время, как максимум, квадратичное относительно длины этой формулы. Для этого используются законы Де Моргана и закон двойного отрицания.