Overview of showing problems to be NP-complete

The techniques we use to show that a particular problem is NP-complete differ from the techniques used throughout most of this book to design and analyze algorithms. There is a fundamental reason for such a difference: in showing a problem to be NP-complete, we are making a statement about how hard it is (or at least how hard we think it is), not about how easy it is. We are not trying to prove the existence of an efficient algorithm, but rather that no efficient algorithm is likely to exist. In this way, NP-completeness proofs are somewhat like the proof in Section 8.1 of an Ω(n lg n)-time lower bound for any comparison sort algorithm; the specific techniques used for showing NP-completeness differ from the decision-tree method used in Section 8.1, however.

We rely on three key concepts in showing a problem to be NP-complete: