NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Версия от 15:21, 17 марта 2010; 192.168.0.2 (обсуждение) (→Доказательство принадлежности классу NP)
Содержание
Определения
- Литералом является переменная или отрицание переменной. Например, или .
- Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например,
- Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.
Определение
SAT — задача о выполнимости булевой формулы в форме КНФ.
в КНФ,Теорема
Доказательство
Для доказательства теоремы необходимо установить два факта:
Доказательство принадлежности классу NP
В качестве сертификата выберем набор литералов
, представляющий собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности. Таким образом,