In this chapter, we will concentrate on techniques for proving that no efficient algorithm exists for a given problem. The practical reader is probably squirming at the notion of proving anything and will be particularly alarmed at the idea of investing time to prove that something does not exist. Why will you be better off knowing that something you don't know how to do in fact can't be done at all?
The truth is that the theory of NP-completeness is an immensely useful tool for the algorithm designer, even though all it does is provide negative results. That noted algorithm designer Sherlock Holmes once said, ``When you have eliminated the impossible, what remains, however improbable, must be the truth.'' The theory of NP-completeness enables the algorithm designer to focus her efforts more productively, by revealing that the search for an efficient algorithm for this particular problem is doomed to failure. When one fails to show that a problem is hard, that means there is likely an algorithm that solves it efficiently. Two of the war stories in this book describe happy results springing from bogus claims of hardness.
The theory of NP-completeness also enables us to identify exactly what properties make a particular problem hard, thus providing direction for us to model it in different ways or exploit more benevolent characteristics of the problem. Developing a sense for which problems are hard and which are not is a fundamental skill for algorithm designers, and it can come only from hands-on experience proving hardness.
We will not discuss the complexity-theoretic aspects of NP-completeness in depth, limiting our treatment to the fundamental concept of reductions, which show the equivalence of pairs of problems. For a discussion, we refer the reader to [GJ79], the truly essential reference on the theory of intractability.
The take-home lessons from this chapter are: