Source code online books for professionals by professionals

Figure 11-1.  Two uses of reduction: reducing an unknown problem to an easy one or reducing a hard problem to an 
unknown one. In the latter case, the unknown problem must be as hard as the known one
Now look at the second image. Here, a known, hard problem is reduced to the unknown problem u. Can we have 
an edge from u to the ground (like the gray edge in the figure)? That would give us a path from h to the ground—but 
such a path cannot exist, or h wouldn’t be hard!
In the following, I’ll be using this basic idea not only to show that problems are hard but also to define some 
notions of hardness. As you may (or may not) have noticed, there is some ambiguity in the term hard here. It can 
basically have two different meanings:
The problem is intractable—any algorithm solving it must be exponential.
•
We don’t know whether the problem is intractable, but no one has ever been able to find a 
•
polynomial algorithm for it.
The first of these means that the problem is hard for a computer to solve, while the second means that it’s hard 
for people (and maybe computers as well). Take another look at the rightmost image in Figure 
11-1
. How would the 
two meaning of “hard” work here? Let’s take the first case: We know that h is intractable. It’s impossible to solve it 
efficiently. A solution to u (that is, a reduction to ground) would imply a solution to h, so no such solution can exist. 
Therefore, u must also be intractable.
The second case is a bit different—here the hardness involves a lack of knowledge. We don’t know if problem 
h is intractable, although we know that it seems difficult to find a solution. The core insight is still that if we reduce 
h to u, then u is at least as hard as h. If h is intractable, then so is u. Also, the fact that many people have tried to find 
a solution to h makes it seem less likely that we’ll succeed, which also means that it may be improbable that u is 

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
230
tractable. The more effort has been directed at solving h, the more astonishing it would be if u were tractable (because 
then so would h). This is, in fact, exactly the situation for a whole slew of practically important problems: We don’t 
know if they’re intractable, but most people are still highly convinced that they are. Let’s take a closer look at these 
rascal problems.