30 1. Classical Computation
is some y such that |y| q(|x|) and R(x, y). Therefore M has, for x, a
computational path of polynomial length ending with “yes”. If x / L, no
computational path ends with “yes”.
Now we proceed to yet another description of NP that is just a refor-
mulation of Definition 3.2, but which has a form that can be used to define
other complexity classes.
Definition 3.3. Imagine two persons: King Arthur, whose mental abilities
are polynomially bounded, and a wizard Merlin, who is intellectually om-
nipotent and knows everything. A is interested in some property L(x) (he
wants, for example, to be sure that some graph x has a Hamiltonian cycle).
M wants to convince A that L(x) is true. But A does not trust M (“he
is too clever to be loyal”) and wants to make sure L(x) is true, not just
believe M.
So Arthur arranges that, after both he and Merlin see input string x,
M writes a note to A where he “proves” that L(x) is true. Then A verifies
this proof by some polynomial proof-checking procedure.
The proof-checking procedure is a polynomial predicate
R(x, y) = “y is a proof of L(x)”.
It should satisfy two properties:
L(x) = 1 M can convince A that L(x) is true by presenting some
proof y such that R(x, y);
L(x) = 0 whatever M says, A is not convinced: R(x, y) is false for
any y.
Moreover, the proof y should have polynomial (in |x|) length, otherwise
A cannot check R(x, y) in polynomial (in |x|) time.
In this way, we arrive precisely at Definition 3.2.
3.2. Reducibility and NP-completeness. The notion of reducibility al-
lows us to verify that a predicate is at least as difficult as some other pred-
icate.
Definition 3.4 (Karp reducibility). A predicate L1 is reducible to a pred-
icate L2 if there exists a function f P such that L1(x) = L2(f(x)) for any
input string x.
We say that f reduces L1 to L2. Notation: L1 L2.
Karp reducibility is also called “polynomial reducibility” (or just “re-
ducibility”).
Lemma 3.2. Let L1 L2. Then
(a) L2 P L1 P;
http://dx.doi.org/10.1090/gsm/047/05
Previous Page Next Page