220 NONDETERMINISTIC ALGORITHMS
another NP-complete problem, to them. A 1979 book by Garey and Johnson
lists hundreds of problems that have been shown to be NP-complete.
The power of the reduction process is that if any NP-complete problem can
be reduced to a class P problem, all of the NP problems must have polynomial
time solutions. So far, all attempts at reductions of this type have failed.8.2 Typical NP Problems
Each of the problems that we will discuss can be viewed as either an optimiza-
tion problem or a decision problem. Optimization problems look for a specific
result that is usually a minimum or maximum value. Decision problems look at
a limit and ask if there is a solution that has a value above (for maximization
problems) or below (for minimization problems) the limit provided. Optimiza-
tion problems will supply as their result an answer to the problem, whereas
decision problems will reply with just a yes or no answer.
In Section 8.1, we discussed the traveling salesperson problem. In that sec-
tion, we discussed the optimization version of this problem. This is a minimiza-
tion problem and so we were interested in finding the path that has the lowest
cost. This problem can also be presented as a decision problem. For the travel-
ing salesperson decision problem, we would ask if there is a path that has a cost
below some limit C. Obviously, decision problem answers will vary based on
the limit provided. In cases where the limit is very large (perhaps larger than
the total of all the costs), an answer of yes might be easy to provide. In cases
where the limit is very small (perhaps smaller than the costs to travel between
any two cities), an answer of no might be easy to provide. For most other pos-
sibilities, the time to determine an answer is very long and related to the time
needed to solve the optimization version. For this reason, we will talk about
the optimization and decision versions interchangeably and at different times
will use the one that is most appropriate for the discussion.
In the next few sections, a set of six additional NP problems will be
described in both their optimization and decision form.■ 8.2.1 Graph Coloring
As was discussed in Chapter 6, a graph G = (V,E) is a set of vertices or nodes
(V) and a set of edges (E) that connect pairs of nodes. For this problem, we
will only be concerned with undirected graphs. We can color a graph by