Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 6.2. Разрешимость системы уравнений Up: 6. Примеры NP-полных задач Previous: 6. Примеры NP-полных задач Contents: Содержание

6.1. 3-КНФ

Эта задача задается предикатом

$3\text{-}SAT(x)=1$ $\Longrightarrow$ есть 3-КНФ, которая истинна при некоторых значениях переменных. 3-КНФ - это конъюнкция дизъюнкций, каждая из которых содержит три литерала, а литерал - это переменная или ее отрицание.

$3\text{-}SAT(x)=0$ $\Longrightarrow$ есть 3-КНФ, которая ложна при всех значениях переменных.

$3\text{-}SAT$ также $\ensuremath{\mathrm {NP}}$ -полна. Это устанавливается сведением к ней .

Теорема 2. $SAT\propto 3\text{-}SAT$ .

Доказательство. Рассмотрим вычисление истинности заданной формулы $\varphi(x_1,\dots,x_n)$ , использующей связки $(\neg, \vee, \wedge)$ . Результаты промежуточных вычислений обозначим $y_1,\dots, y_s$ . Для каждой переменной выполнено одно из трех равенств

$\begin{displaymath} \begin{split} y_k&= u\vee v,\\ y_k&= u\wedge v,\\ y_k&= \neg v, \end{split}\end{displaymath}$ (7)

где

либо переменные формулы, либо уже определенные вспомогательные переменные, т. е. $u,v\in\{x_1,\dots,x_n,y_1,\dots,y_{k-1}\}$ .

Теперь запишем 3-КНФ, равносильную исходной формуле $\varphi(\cdot)$ . В эту КНФ будут входить переменные $x_1,\dots,x_n$ и $y_1,\dots, y_s$ . Построим вначале конъюнкцию условий, означающих, что каждая из вспомогательных переменных имеет значение, задаваемое формулой (7). Есть три типа таких условий и каждый можно записать в виде 3-КНФ:
$\begin{align*} \big(y\Leftrightarrow( x_1\vee x_2)\big) &= (x_1\vee x_2\vee\neg ... ...g(y\Leftrightarrow\neg x\big)&= (x\vee y)\wedge(\neg x\vee \neg y). \end{align*}$
Подставляя эти 3-КНФ в , получим 3-КНФ . Искомая 3-КНФ имеет вид $K=K'\wedge y_s$ . Действительно, истинность равносильна утверждению: все присваивания выполнены правильно и в результате получилась 1 (). Значит, если при каких-то значениях переменных формула $\varphi$ истинна, то 3-КНФ выполнима, и наоборот. $\qedsymbol$

МЦНМО

Написать комментарий