3. The class NP: Reducibility and completeness 31

(b) L1 / ∈ P ⇒ L2 / ∈ P;

(c) L2 ∈ NP ⇒ L1 ∈ NP.

Proof. To prove (a) let us note that |f(x)| = poly(|x|) for any f ∈ P.

Therefore, we can decide L1(x) in polynomial time as follows: we compute

f(x) and then compute L2(f(x)).

Part (b) follows from (a).

Part (c) is also simple. It can be explained in various ways. Using the

Arthur–Merlin metaphor, we say that Merlin communicates to Arthur a

proof that L2(f(x)) is true (if it is true). Then Arthur computes f(x) by

himself and checks whether L2(f(x)) is true, using Merlin’s proof.

Using Definition 3.2, we can explain the same thing as follows:

L1(x) ⇔ L2(f(x)) ⇔ ∃ y

(

|y| q(|f(x)|)

)

∧ R(f(x),y)

⇔ ∃ y

(

|y| r(|x|)

)

∧ R (x, y) .

Here R (x, y) stands for

(

|y| q(|f(x)|)

)

∧ R(f(x),y), and r(n) = q(h(n)),

where h(n) is a polynomial bound for the time needed to compute f(x) for

any string x of length n (and, therefore, |f(x)| ≤ h(|x|) for any x).

Definition 3.5. A predicate L ∈ NP is NP-complete if any predicate in NP

is reducible to it.

If some NP-complete predicate can be computed in time T(n), then any

NP-predicate can be computed in time poly(n) + T(poly(n)). Therefore, if

some NP-complete predicate belongs to P, then P = NP. Put is this way:

if P = NP (which is probably true), then no NP-complete predicate belongs

to P.

If we measure running time “up to a polynomial”, then we can say that

NP-complete predicates are the “most diﬃcult” ones in NP.

The key result in computational complexity says that NP-complete pred-

icates do exist. Here is one of them, called satisfiability: SAT (x) means that

x is a propositional formula (containing Boolean variables and operations

¬, ∧, and ∨) that is satisfiable, i.e., true for some values of the variables.

Theorem 3.3 (Cook, Levin).

(1) SAT ∈ NP;

(2) SAT is NP-complete.

Corollary. If SAT ∈ P, then P = NP.

Proof of Theorem 3.3. (1) To convince Arthur that a formula is satisfi-

able, Merlin needs only to show him the values of the variables that make it

true. Then Arthur can compute the value of the whole formula by himself.