Complexity Classes - Models of Computation: Exploring the Power of Computing - page 336

Figure 8.4 A graph on which the TRAVELING SALESPERSON problem is defined. The heavy
edges identify a shortest tour.

ministically in exponential time by enumerating all tours and choosing the one with smallest
length. (See Problem 8.9 .)
The TRAVELING SALESPERSON decision problem is a reduction of the traveling sales-
person optimization problem , whose goal is to find the shortest tour that visits each city
once. The output of the optimization problem is an ordering of the cities that has the short-
est tour. By contrast, the TRAVELING SALESPERSON decision problem reports that there is
or is not a tour of length k or less. Given an algorithm for the optimization problem, the
decision problem can be solved by calculating the length of an optimal tour and comparing
it to the parameter k of the decision problem. Since the latter steps can be done in polyno-
mial time, if the optimization algorithm can be done in polynomial time, so can the decision
problem. On the other hand, given an algorithm for the decision problem, the optimization
problem can be solved through bisection as follows: a) Since the length of the shortest tour
is in the interval [ n min i , j d i , j , n max i , j d i , j ] , invoke the decision algorithm with k equal to
the midpoint of this interval. b) If the instance is a “yes” instance, let k be the midpoint
of the lower half of the current interval; if not, let it be the midpoint of the upper half. c)
Repeat the previous step until the interval is reduced to one integer. The interval is bisected
O (log n (max i , j d i , j − min i , j d i , j )) times. Thus, if the decision problem can be solved in

polynomial time, so can the optimization problem.
Whether P = NP is one of the outstanding problems of computer science. The current
consensus of complexity theorists is that nondeterminism is such a powerful specification de-
vice that they are not equal. We return to this topic in Section 8.8 .

8.5.1 Space and Time Hierarchies
In this section we state without proof the following time and space hierarchy theorems. (See
[ 127 , 128 ].) These theorems state that if one space (or time) resource bound grows sufficiently
rapidly relative to another, the set of languages recognized within the first bound is strictly
larger than the set recognized within the second bound.

THEOREM 8.5.1 (Time Hierarchy Theorem) If r ( n ) ≥ n is a proper complexity function,
then TIME ( r ( n )) is strictly contained in TIME ( r ( n )log r ( n )) .