8.1 WHAT IS NP? 217algorithm produces, you might find that the paths you put together take you
to a node more than once. The second difference is that we are expected to
return to the starting point in the traveling salesperson problem, whereas the
shortest-path algorithm has no such expectation.
Our brief discussion of the extremely large number of possible orderings of
the nodes should convince you that a deterministic algorithm that examines all
of the different orders of nodes would take an extremely long time to com-
plete. To show that this algorithm is in the class NP, we need to show how a
two-step process as described above would solve it. For the traveling salesper-
son problem, the first step would be to nondeterministically generate a list of
the cities. Because this process is nondeterministic, each time it is run, a differ-
ent order of the cities will be generated. Obviously this generation process can
be done in polynomial time, because we can keep a list of city names, generate
a random number, output the corresponding city name, and then remove that
name from the list to prevent it from appearing twice. This process would run
in order O(N) where N is the number of cities. The second step would be to
determine the cost of traveling to the cities in the order specified. To deter-
mine this, we would simply have to look at the cost for each successive pair of
cities in the list, which would have complexity O(N^2 ) in the worst case.
Because both of these steps are of polynomial complexity, the traveling sales-
person problem is in the class NP. Notice that it is the potential number of
times that this would have to be done that makes this problem so time con-
suming.
At this point, you might notice that we could use this two-step process for
any of our previous algorithms. For example, we could have sorted a list by
outputting a random order of the original list and then checking to see if the
elements are in increasing order. Doesn’t this make sorting a member of the
class NP? Yes it does. The difference between a problem in class P and one just
in class NP is that, in the former case, we also have a deterministic algorithm
that runs in polynomial time, whereas in the later we don’t. We will discuss this
issue again in Section 8.3.
■ 8.1.1 Problem Reductions
One way that we can get a solution to a problem is through the concept of a
reduction. If we can reduce one problem to another, we could use an algo-
rithm for the second problem to get a solution and then transform this
answer into a solution for the first problem. If we can do the transformations