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

input.

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: