32 1. Classical Computation
(2) Let L(x) be an NP-predicate and
L(x) = ∃y
∧ 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
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-
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).