NP-полнота задачи о выполнимости булевой формулы в форме КНФ — различия между версиями
(→Доказательство принадлежности классу NPH) |
м (rollbackEdits.php mass rollback) |
||
(не показано 15 промежуточных версий 5 участников) | |||
Строка 7: | Строка 7: | ||
== Теорема == | == Теорема == | ||
− | <tex> CNFSAT \in NPC | + | <tex> CNFSAT \in NPC </tex>, то есть задача [[NP-полнота|NP-полная]]. |
+ | |||
== Доказательство == | == Доказательство == | ||
Для доказательства теоремы необходимо установить два факта: | Для доказательства теоремы необходимо установить два факта: | ||
Строка 13: | Строка 14: | ||
* <tex> CNFSAT \in NPH </tex> | * <tex> CNFSAT \in NPH </tex> | ||
==== Доказательство принадлежности классу NP ==== | ==== Доказательство принадлежности классу NP ==== | ||
− | В качестве сертификата выберем множество <tex> \{y_1, ...,y_n\} </tex>, представляющее собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу <tex> \phi(x_1, ..., x_n) </tex> и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности. Таким образом, <tex> CNFSAT \in | + | В качестве сертификата выберем множество <tex> \{y_1, ...,y_n\} </tex>, представляющее собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу <tex> \phi(x_1, ..., x_n) </tex> и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности. Таким образом, <tex> CNFSAT \in NP </tex> |
==== Доказательство принадлежности классу NPH ==== | ==== Доказательство принадлежности классу NPH ==== | ||
Строка 25: | Строка 26: | ||
* Второй этап - переписать формулу, которая представляет собой логическое '''И''' и '''ИЛИ''' литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы. Рассмотрим дерево разбора произвольной формулы. Листья этого дерева будут соответствовать литералам, а узлы - логической операции '''И''' или '''ИЛИ''' над двумя его потомками. | * Второй этап - переписать формулу, которая представляет собой логическое '''И''' и '''ИЛИ''' литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы. Рассмотрим дерево разбора произвольной формулы. Листья этого дерева будут соответствовать литералам, а узлы - логической операции '''И''' или '''ИЛИ''' над двумя его потомками. | ||
− | # Для узла с меткой '''И''' соответствующая КНФ получается как конъюнкция ('''И''') всех дизъюнктов двух подформул <tex> \alpha </tex> и <tex> \beta </tex>. | + | # Для узла с меткой '''И''' соответствующая КНФ получается как конъюнкция ('''И''') всех дизъюнктов двух подформул <tex> \alpha </tex> и <tex> \beta </tex>, уже находящихся в КНФ. |
− | # Для узла с меткой '''ИЛИ''' нужно ввести новую переменную. Добавляем ее во все дизъюнкты левого операнда <tex> \alpha </tex> и ее отрицание во все дизъюнкты правого операнда <tex> \beta </tex>. | + | # Для узла с меткой '''ИЛИ''' нужно ввести новую переменную. Добавляем ее во все дизъюнкты левого операнда <tex> \alpha </tex> и ее отрицание во все дизъюнкты правого операнда <tex> \beta </tex>. Заметим, что формула <tex> \alpha \vee \beta </tex> выполнима тогда и только тогда, когда выполнима <tex> (\alpha \vee y) \wedge (\beta \vee \neg y), </tex> где <tex> y </tex> - новая переменная. После чего, воспользовавшись законами преобразования в каждой формуле в скобках, получим формулы в КНФ: <tex> \alpha \vee y = ((...)\wedge(...)\wedge ... \wedge(...)) \vee y = (...\vee y)\wedge(...\vee y)\wedge...\wedge(...\vee y). </tex> Аналогично преобразуем <tex> \beta \vee \neg y </tex>. |
− | + | Каждый раз новая формула увеличивается не более, чем на количество листьев в поддереве, а значит максимальный размер формулы <tex> \omega </tex> можно представить как ''(число листьев) * (число вершин)'', что соответствует оценке работы алгоритма <tex> O(|\phi|^2) </tex>. Таким образом, условия сведения выполнены, и действительно <tex> CNFSAT \in NPH </tex>. | |
+ | |||
+ | Теорема доказана. | ||
+ | |||
+ | [[Категория:NP]] |
Текущая версия на 19:28, 4 сентября 2022
Определения
- Литералом является переменная или отрицание переменной. Например, или .
- Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например,
- Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.
Определение
SAT — задача о выполнимости булевой формулы в форме КНФ.
в КНФ,Теорема
Доказательство
Для доказательства теоремы необходимо установить два факта:
Доказательство принадлежности классу NP
В качестве сертификата выберем множество
, представляющее собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности. Таким образом,Доказательство принадлежности классу NPH
Выполним сведение по Карпу задачи к задаче . Для этого необходимо построить функцию , вычислимую за полиномиальное время от длины входа, которая выполняла бы преобразование , где в КНФ. Заметим, что в общем случае время построения эквивалентной формулы в форме КНФ может оказаться больше полиномиального. В частности, длина формулы может вырасти экспоненциально, и тогда время порождения тоже экспоненциально вырастет. Однако нам достаточно предъявить формулу , которая будет выполнима тогда и только тогда, когда выполнима исходная формула . При этом формулы могут оказаться не эквивалентными, ввиду, например, добавления новых переменных.
Итак, опишем действия функции
.- На первом этапе все отрицания спускаются вниз по дереву выражения, так что в формуле остаются только отрицания переменных. Булева формула превращается в логические И и ИЛИ литералов. Это преобразование дает формулу, эквивалентную исходной, и занимает время, как максимум, квадратичное относительно длины этой формулы. Для этого используются законы Де Моргана и закон двойного отрицания.
- Второй этап - переписать формулу, которая представляет собой логическое И и ИЛИ литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы. Рассмотрим дерево разбора произвольной формулы. Листья этого дерева будут соответствовать литералам, а узлы - логической операции И или ИЛИ над двумя его потомками.
- Для узла с меткой И соответствующая КНФ получается как конъюнкция (И) всех дизъюнктов двух подформул и , уже находящихся в КНФ.
- Для узла с меткой ИЛИ нужно ввести новую переменную. Добавляем ее во все дизъюнкты левого операнда и ее отрицание во все дизъюнкты правого операнда . Заметим, что формула выполнима тогда и только тогда, когда выполнима где - новая переменная. После чего, воспользовавшись законами преобразования в каждой формуле в скобках, получим формулы в КНФ: Аналогично преобразуем .
Каждый раз новая формула увеличивается не более, чем на количество листьев в поддереве, а значит максимальный размер формулы
можно представить как (число листьев) * (число вершин), что соответствует оценке работы алгоритма . Таким образом, условия сведения выполнены, и действительно .Теорема доказана.