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)|)
|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 difficult” 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.
Previous Page Next Page