Source code online books for professionals by professionals

reDUCtION BY SUBprOBLeM
While the idea of showing hardness by using reductions can be a bit abstract and strange, there is one special 
case (or, in some ways, a different perspective) that can be easy to understand: if your problem has a hard 
subproblem, then the problem as a whole is (obviously) hard. In other words, if solving your problem means that 
you also have to solve a problem that is known to be hard, you’re basically out of luck. For example, if your boss 
asks you to create an antigravity hoverboard, you could probably do a lot of the work, such as crafting the board 
itself or painting on a nice pattern. however, actually solving the problem of circumventing gravity makes the 
whole endeavor doomed from the start.
so, how is this a reduction? It’s a reduction, because you can still use your problem to solve the hard subproblem. 
In other words, if you’re able to build an antigravity hoverboard, then your solution can (again, quite obviously) 
be used to circumvent gravity. the hard problem isn’t even really transformed, as in most reductions; it’s just 
embedded in a (rather irrelevant) context. or consider the loglinear lower bound on the worst-case running time 
for general sorting. If you were to write a program that took in a set of objects, performed some operations on 
them, and then output information about the objects in sorted order, you probably couldn’t do any better than 
loglinear in the worst case.
but why “probably”? because it depends on whether there’s a real reduction there. Could your program 
conceivably be used as a “sorting machine”? Would it be possible for me, if I could use your program as I wanted, 
to feed it objects that would let me sort any real numbers? If yes, then the bound holds. If no, then maybe it 
doesn’t. For example, maybe the sorting is based on integers that can be sorted using counting sort? or maybe 
you actually create the sorting keys yourself, so the objects can be output in any order you please? the question 
of whether your problem is expressive enough—whether it can express the general sorting problem. this is, in 
fact, one of the key insights of this chapter: that problem hardness is a matter of expressiveness.
Not in Kansas Anymore?
As I wrote this chapter for the first edition, the excitement had only just started dying down around the Internet 
after a scientific paper was published online, claiming to prove to have solved the so-called P versus NP problem, 
concluding that P does not equal NP.
3
 Although the emerging consensus is that the proof is flawed, the paper created 
a tremendous interest—at least in computer science circles. Also, less credible papers with similar claims (or the 
converse, that P equals NP) keep popping up at regular intervals. Computer scientists and mathematicians have been 
working on this problem since the 1970s, and there’s even a million-dollar prize for the solution.
4
 Although much 
progress has been made in understanding the problem, no real solution seems forthcoming. Why is this so hard? And 
why is it so important? And what on Earth are P and NP?
3
Vinay Deolalikar. P is not equal to NP. August 6, 2010.
4
http://www.claymath.org/millennium-problems

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
231
The thing is, we don’t really know what kind of a world we’re living in. To use The Wizard of Oz as an analogy—we 
may think we’re living in Kansas, but if someone were to prove that P = NP, we’d most definitely not be in Kansas 
anymore. Rather, we’d be in some kind of wonderland on par with Oz, a world Russel Impagliazzo has christened 
Algorithmica.
5
 What’s so grand about Algorithmica, you say? In Algorithmica, to quote a well-known song, “You never 
change your socks, and little streams of alcohol come trickling down the rocks.” More seriously, life would be a lot less 
problematic. If you could state a mathematical problem, you could also solve it automatically. In fact, programmers 
no longer would have to tell the computer what to do—they’d only need to give a clear description of the desired 
output. Almost any kind of optimization would be trivial. On the other hand, cryptography would now be very hard 
because breaking codes would be so very, very easy.
The thing is, P and NP are seemingly very different beasts, although they’re both classes of problems. In fact, 
they’re classes of decision problems, problems that can be answered with yes or no. This could be a problem such as 
“Is there a path from s to t with a weight of at most w?” or “Is there a way of stuffing items in this knapsack that gives 
me a value of at least v?” The first class, P, is defined to consist of those problems we can solve in polynomial time (in 
the worst case). In other words, if you turn almost any of the problems we’ve looked at so far into a decision problem, 
the result would belong to P.
NP seems to have a much laxer definition
6
: It consists of any decision problems that can be solved in polynomial 
time by a “magic computer” called a nondeterministic Turing machine, or NTM. This is where the N in NP comes 
from—NP stands for “nondeterministically polynomial.” As far as we know, these nondeterministic machines are 
super-powerful. Basically, at any time where they need to make a choice, they can just guess, and by magic, they’ll 
always guess right. Sounds pretty awesome, right?
Consider the problem of finding the shortest path from s to t in a graph, for example. You already know quite a bit 
about how to do this with algorithms of the more … nonmagical kind. But what if you had an NTM? You’d just start in 
s and look at the neighbors. Which way should you go? Who knows—just take a guess. Because of the machine you’re 
using, you’ll always be right, so you’ll just magically walk along the shortest path with no detours. For such a problem 
as the shortest path in a DAG, for example, this might not seem like such a huge win. It’s a cute party trick, sure, but 
the running time would be linear either way.
But consider the first problem in Chapter 1: visiting all the towns of Sweden exactly once, as efficiently as possible. 
Remember how I said it took about 85 CPU-years to solve this problem with state-of-the-art technology a few years ago? 
If you had an NTM, you’d just need one computation step per town. Even if your machine were mechanical with a hand 
crank, it should finish the computation in a matter of seconds. This does seem pretty powerful, right? And magical?
Another way of describing NP (or, for that matter, nondeterministic computers) is to look at the difference 
between solving a problem and checking a solution. We already know what solving a problem means. If we are to