Source code online books for professionals by professionals

Figure 11-2.  An NP-complete problem is a problem in NP that is at least as hard as all the others. That is, all the 
problems in NP can be reduced to it

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
234
For example, we can sum all the edge weights, and we get an upper limit C on the cost of the TSP tour, with 0 as a 
lower limit. We then tentatively guess that the minimum value is C/2 and solve the decision problem, “Is there a tour 
of length at most C/2?” We get a yes or a no in polynomial time and can then keep bisecting the upper or lower half of 
the value range. Exercise 11-1 asks you to show that the resulting algorithm is polynomial.
Tip
 
■
   this strategy of bisecting with a black box can be used in other circumstances as well, even outside the context 
of complexity classes. If you have an algorithm that lets you determine whether a parameter is large enough, you can 
bisect to find the right/optimal value, at the cost of a logarithmic factor. Quite cheap, really.
In other words, even though much of complexity theory focuses on decision problems, optimization problems 
aren’t all that different. In many contexts, you may hear people use the term NP-complete when what they really 
mean is NP-hard. Of course, you should be careful about getting things right, but whether you show a problem to be 
NP-hard or NP-complete is not all that crucial for the practical purpose of arguing its hardness. (Just make sure your 
reductions are in the right direction!)