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