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 diﬃcult 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