Задача о выполнимости

Задача о выполнимости (Satisfiability problem) — одна из основных $\mathcal NP$ -полных задач. Формулируется следующим образом.

У с л о в и е. Задано множество булевых переменных $V$ и правильно построенное булево выражение $E$ над $V$ .

В о п р о с. Существует ли набор значений переменных множества $V$ , при котором выражение $E$ выполнено, т.е. принимает значение "истина"?

Можно показать, что даже при более жестких ограничениях на вид формулы задача выполнимости булевых формул также ${\mathcal NP}$ -полна.

Булева формула находится в конъюнктивной нормальной форме (КНФ), если она представляет собой произведение сумм литералов, где каждый литерал имеет вид $x$ или $\lnot x$ для некоторой переменной $x$ . Задача выполнимости формул, находящихся в КНФ, ${\mathcal NP}$ -полна.

Говорят, что булева формула находится в $k$ -конъюнктивной нормальной форме ( $k$ -КНФ), если она представляет собой произведение сумм, состоящих не более чем из $k$ литералов. Задача $k$ -выполнимости ( $k$ -ВЫП) состоит в выяснении выполнимости формулы, находящейся в $k$ -КНФ.

Для $k=1$ и 2 известны полиномиальные алгоритмы, проверяющие $k$ -выполнимость, т.е. 1-ВЫП, 2-ВЫП $\in \mathcal NP$ . Ситуация изменяется при $k=3$ , поскольку задача о 3-выполнимости является ${\mathcal NP}$ - полной.