32 1. Classical Computation

(2) Let L(x) be an NP-predicate and

L(x) = ∃y

(

|y| q(|x|)

)

∧ R(x, y)

for some polynomial q and some predicate R decidable in polynomial time.

We need to prove that L is reducible to SAT. Let M be a Turing machine

that computes R in polynomial time. Consider the computation table (see

the proof of Theorem 2.2) for M working on some input x#y. We will use

the same variables as in the proof of Theorem 2.2. These variables encode

the contents of cells in the computation table.

Now we write a formula that says that values of variables form an en-

coding of a successful computation (with answer “yes”), starting with the

input x#y. To form a valid computation table, values should obey some

local rules for each four cells configured as follows:

These local rules can be written as formulas in 4t variables (if t variables are

needed to encode one cell). We write the conjunction of these formulas and

add formulas saying that the first line contains the input string x followed

by # and some binary string y, and that the last line contains the answer

“yes”.

The satisfying assignment for our formula will be an encoding of a suc-

cessful computation of M on input x#y (for some binary string y). On the

other hand, any successful computation that uses at most S tape cells and

requires at most T steps (where T × S is the size of the computation table

that is encoded) can be transformed into a satisfying assignment.

Therefore, if we consider a computational table that is large enough to

contain the computation of R(x, y) for any y such that |y| q(|x|), and

write the corresponding formula as explained above, we get a polynomial-

size formula that is satisfiable if and only if L(x) is true. Therefore L is

reducible to SAT .

Other examples of NP-complete problems (predicates) can be obtained

using the following lemma.

Lemma 3.4. If SAT ∝ L and L ∈ NP, then L is NP-complete. More

generally, if L1 is NP-complete, L1 ∝ L2, and L2 ∈ NP, then L2 is NP-

complete.

Proof. The reducibility relation is transitive: if Ll ∝ L2 and L2 ∝ L3, then

L1 ∝ L3. (Indeed, the composition of two functions from P belongs to P).