224 NONDETERMINISTIC ALGORITHMS
8.3 What Makes Something NP?
We have looked at a lot of problems that are in the class P and a handful that
are in the class NP. We described the class NP as those problems that are solv-
able in polynomial time by a nondeterministic algorithm. As was mentioned,
we could describe the process of sorting as follows:- Nondeterministically output the elements of a list.
- Check to see if si < si+1 for i = 1 through N 1.
This describes a two-step nondeterministic process. The first step takes no
comparisons and will be completed in N steps, each outputting one element.
The second step is also polynomial time because it only does N 1 compari-
sons. This process fits our definition of the class NP, so it would seem that sort-
ing is in the class NP as well as the class P. Because we can do this with any
algorithm, all algorithms in the class P are also in the class NP. In the case of
problems just in class NP, there is, however, no known deterministic polyno-
mial time algorithms. This makes P a subset of NP, but at present there are
problems in NP that are not known to be in P.
The heart of this difference is really the large number of combinations that
we must necessarily examine for these NP problems. But it’s a little more com-
plex than just the number of combinations of input values. We can have a list of
30 distinct elements or a list of 30 distinct cities. In the both cases, there are 30!
combinations of these 30 elements or cities and only one of these can be cor-
rectly sorted or can be a shortest path. The difference is that we have polyno-
mial time algorithms that will create the correctly sorted list, some in as few as
150 comparisons. For bubble sort, the first pass through the list will at mini-
mum put the last element into the correct place in the list, eliminating with 29
comparisons at least 1 / 30 of the possible combinations. On the second pass,
28 comparisons will eliminate at least 1 / 29 of the combinations that are still
left. When we look at the process closer, we see that even more of the possibil-
ities might get eliminated, because each pass of the algorithm might not only
move the next largest element to the end of the list but also fix other elements
that are out of order.
The best we can do to find the shortest path is to examine all of the possible
paths to see which has the shortest length. We don’t have an algorithm that,
with a few operations, can successfully eliminate a significant number of the