3. The class NP: Reducibility and completeness 33
According to the hypothesis, any NP-problem is reducible to L1, and L1 is
reducible to L2. Therefore any NP-problem is reducible to L2.
Now let us consider the satisfiability problem restricted to 3-CNF. Recall
that a CNF (conjunctive normal form) is a conjunction of clauses; each
clause is a disjunction of literals; each literal is either a variable or a negation
of a variable. If each clause contains at most three literals, we get a 3-CNF.
By 3-SAT we denote the following predicate:
3-SAT(x) = x is a satisfiable 3-CNF.
Evidently, 3-SAT is reducible to SAT (because any 3-CNF is a formula).
The next theorem shows that the reverse is also true: SAT is reducible to
3-SAT. Therefore 3-SAT is NP-complete (by Lemma 3.4).
Theorem 3.5. SAT 3-SAT.
Proof. For any propositional formula (and even for any circuit over the
standard basis {AND, OR, NOT}), we construct a 3-CNF that is satisfiable
if and only if the given formula is satisfiable (the given circuit produces
output 1 for some input).
Let x1,...,xn be input variables of the circuit, and let y1,...,ys be
auxiliary variables (see the definition of a circuit). Each assignment involves
at most three variables (1 on the left-hand side, and 1 or 2 on the right-hand
side).
Now we construct a 3-CNF that has variables x1,...,xn,y1,...,ys and
is true if and only if the values of all yj are correctly computed (i.e., they
coincide with the right-hand sides of the assignments) and the last variable is
true. To this end, we replace each assignment by an equivalence (of Boolean
expressions) and represent this equivalence as a 3-CNF:
(
y (x1 x2)
)
= (x1 x2 ¬y) (¬x1 x2 y) (x1 ¬x2 y)
(¬x1 ¬x2 y),
(
y (x1 x2)
)
= (x1 x2 ¬y) (¬x1 x2 ¬y) (x1 ¬x2 ¬y)
(¬x1 ¬x2 y),
(
y ¬x
)
= (x y) (¬x ¬y).
Finally, we take the conjunction of all these 3-CNF’s and the variable ys
(the latter represents the condition that the output of the circuit is 1).
Let us assume that the resulting 3-CNF is satisfied by some x1,...,xn,
y1,...,ys. If we plug the same values of x1,...,xn into the circuit, then
the auxiliary variables will be equal to y1,...,ys, so the circuit output will
be ys = 1. Conversely, if the circuit produces 1 for some inputs, then the
Previous Page Next Page