8.1 WHAT IS NP? 215that we have considered had complexity in O(N^3 ).^1 In fact, the most time-
complex algorithm we examined was matrix multiplication. The bottom line,
however, is that we can get an exact solution to those problems within some
reasonable amount of time. This group of problems is said to be in the class P,
where P stands for polynomial time complexity. Problems for which there is a
polynomial time algorithm are called tractable.
There is another class of problems that are intractable, for which we cur-
rently have no algorithm that will solve the problems in any reasonable amount
of time. These problems are in the class NP, which stands for nondeterministic
polynomial time complexity. The meaning of the phrase “nondeterministic
polynomial time” will become clearer through the rest of this section. The
thing to note is that the only deterministic algorithms that are known to solve
these problems have a complexity that is of exponential or factorial order. For
some problems, the complexity is given by 2N, where N is the number of input
values. In this case, each time we add one additional input value, the amount of
time the algorithm needs to solve the problem would double. If it takes 1024
operations to solve the problem with an input of 10 elements, it would take
2048 operations to solve the problem with an input of 11 elements. This is a
significant increase in time for a small increase in the input.
The name nondeterministic polynomial for problems of the class NP comes
from a two-step process to solve them. In the first step, there is a nondetermin-
istic process that generates a possible solution to the problem. You can see this
as a random guess at the solution that will sometimes be good (the solution or
close to it) and at other times be bad (a far from optimal answer). The second
step will look at the output of the first step and determine if it is a true solu-
tion. Individually, we will see that both of these steps work in polynomial time.
The problem is that we don’t know how many times this process will need to
be repeated before a solution is generated. Even though the individual steps are
polynomial, we may need to call them an exponential or factorial number of
times.
One of the problems in the class NP is the traveling salesperson problem. In
this problem, we are given a set of cities and a “cost” to travel between each of
(^1) Remember that to say a function g(x) is in O(f(x)) means that g(x) grows no faster
thanf(x). So, x^2 is in O(x^3 ).