28 1. Classical Computation
The class NP is defined only for predicates. One says, for example, that
“the property that a graph has a Hamiltonian cycle belongs to NP”. (A
Hamiltonian cycle is a cycle that traverses all vertices exactly once.)
We give several definitions of this class. The first uses nondeterministic
Turing machines. A nondeterministic Turing machine (NTM) resembles
an ordinary (deterministic) machine, but can nondeterministically choose
one of several actions possible in a given configuration. More formally, a
transition function of an NTM is multivalued: for each pair (state, symbol)
there is a set of possible actions. Each action has a form (new state, new
symbol, shift). If the set of possible actions has cardinality at most 1 for
each state-symbol combination, we get an ordinary Turing machine.
A computational path of an NTM is determined by a choice of one of the
possible transitions at each step; different paths are possible for the same
Definition 3.1. A predicate L belongs to the class NP if there exists an
NTM M and a polynomial p(n) such that
L(x) = 1 ⇒ there exists a computational path that gives answer
“yes” in time not exceeding p(|x|);
L(x) = 0 ⇒ (version 1) there is no path with this property;
(version 2) . . . and, moreover, there is no path (of any
length) that gives answer “yes”.
Remark 3.1. Versions 1 and 2 are equivalent. Indeed, let an NTM M1
satisfy version 1 of the definition. To exclude “yes” answers for long com-
putational paths, it suﬃces to simulate M1 while counting its steps, and to
abort the computation after p(|x|) steps.
Remark 3.2. The argument in Remark 3.1 has a subtle error. If the coeﬃ-
cients of the polynomial p are noncomputable, diﬃculties may arise when we
have to compare the number of steps with the value of the polynomial. In
order to avoid this complication we will add to Definition 3.1 an additional
requirement: p(n) has integer coeﬃcients.
Remark 3.3. By definition P ⊆ NP. Is this inclusion strict? Rather intense
although unsuccessful attempts have been made over the past 30 years to
prove the strictness. Recently S. Smale included the P
= NP problem in
the list of most important mathematical problems for the new century (the
other problems are the Riemann hypothesis and the Poincar´e conjecture).
More practical people can dream of $1,000,000 that Clay Institute offers for
the solution of this problem.
Now we give another definition of the class NP, which looks more natu-
ral. It uses the notion of a polynomially decidable predicate of two variables: