3. The class NP: Reducibility and completeness 29

a predicate R(x, y) (where x and y are strings) is polynomially decidable (de-

cidable in polynomial time) if there is a (deterministic) TM that computes)

it in time poly(|x|, |y|) (which means poly(|x|+|y|) or poly

(

max{|x|, |y|} —

these two expressions are equivalent).

Definition 3.2. A predicate L belongs to the class NP if it can be repre-

sented as

L(x) = ∃y

(

|y| q(|x|)

)

∧ R(x, y) ,

where q is a polynomial (with integer coeﬃcients), and R is a predicate of

two variables decidable in polynomial time.

Remark 3.4. Let R(x, y) = “y is a Hamiltonian cycle in the graph x”.

More precisely, we should say: “x is a binary encoding of some graph, and y

is an encoding of a Hamiltonian cycle in that graph”. Take q(n) = n. Then

L(x) means that graph x has a Hamiltonian cycle. (We assume that the

encoding of any cycle in a graph is shorter than the encoding of the graph

itself.)

Theorem 3.1. Definitions 3.1 and 3.2 are equivalent.

Proof. Definition 3.1 ⇒ Definition 3.2. Let M be an NTM and let p(n) be

the polynomial of the first definition. Consider the predicate R(x, y) = “y

is a description of a computational path that starts with input x, ends with

answer ‘yes’, and takes at most p(|x|) steps”. Such a description has length

proportional to the computation time if an appropriate encoding is used

(and even if we use a table as in the proof of Theorem 2.2, the description

length is at most quadratic). Therefore for q(n) in the second definition we

can take O(p(n)) (or

O(p2(n))

if we use less eﬃcient encoding).

It remains to prove that predicate R belongs to P. This is almost obvi-

ous. We must check that we are presented with a valid description of some

computational path (this is a polynomial task), and that this path starts

with x, takes at most p(|x|) steps, and ends with “yes” (that is also easy).

Definition 3.2 ⇒ Definition 3.1. Let R, q be as in Definition 3.2. We

construct an NTM M for Definition 3.1. M works in two stages.

First, M nondeterministically guesses y. More precisely, this means

that M goes to the end of the input string, moves one cell to the right,

writes #, moves once more to the right, and then writes some string y (M’s

nondeterministic rules allow it to write any symbol and then move to the

right, or finish writing). After that, the tape has the form x#y for some y,

and M goes to the second stage.

At the second stage M checks that |y| q(|x|) (note that M can write

a very long y for any given x) and computes R(x, y) (using the polynomial

algorithm that exists according to Definition 3.2). If x ∈ L, then there