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 coefficients), 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
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
if we use less efficient 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
Previous Page Next Page