8.3 WHAT MAKES SOMETHING NP? 225combinations from consideration.^3 So instead, we need to look at all of them.
If we could examine the path length of 1,000,000,000 of the 30! combinations
in 1 second, this would still take more than 840 billion centuries to check all of
the paths. In Chapter 9, we will look at algorithms that will come up with
answers for these problems that approximate the optimal answer. We have no
way of knowing how good an approximation we produce because we don’t
know what the optimal value is. Instead, these algorithms can be run for as
much time as we have available, and the longer they run, the better the answer
they will produce. They may stumble on the optimal answer, but that is not
guaranteed.
So, the thing that puts problems in the class NP is that there are an
extremely large number of possibilities for the optimal answer, and we don’t
have an efficient deterministic algorithm to sift through them to find the cor-
rect one.
■ 8.3.1 Is P = NP?
After the discussion of the previous section, it might seem ridiculous to even
ask if the set of problems in the class P is the same as the set of problems in the
class NP. The discussion showing that there is both a polynomial and nondeter-
ministic polynomial time algorithm for sorting should demonstrate the basis
for the fact that P is a subset of NP. Our discussion of the difference between
sorting and shortest path might lead you to believe that we know that there are
problems in the class NP that are not in the class P. That, however, is not the
correct idea to take away from the last section. All we know at this point is that
we have not been able to find a deterministic polynomial time algorithm that
will solve any of the problems in the class NP. That doesn’t mean that there is
no such algorithm, and researchers are still working to resolve this point. It is
believed that there is no polynomial time solution for the class NP problems,
but how do you prove that a polynomial time algorithm doesn’t exist to solve a
problem? Our best option is to examine the problem and attempt to determine
the lower bound on the work that must be done. At this point, however, no
(^3) It might appear that we could try, for example, to eliminate a path between two cities
that costs a lot. But that simple attempt might not work because it could make us take
a couple of paths that are overall more expensive, so we would not really be better off.
To check to see if eliminating an expensive edge will cause this to happen puts us back
at a high-complexity algorithm.