Chapter notes

The book by Garey and Johnson [110] provides a wonderful guide to NP-completeness, discussing the theory at length and providing a catalogue of many problems that were known to be NP-complete in 1979. The proof of Theorem 34.13 is adapted from their book, and the list of NP-complete problem domains at the beginning of Section 34.5 is drawn from their table of contents. Johnson wrote a series of 23 columns in the Journal of Algorithms between 1981 and 1992 reporting new developments in NP-completeness. Hopcroft, Motwani, and Ullman [153], Lewis and Papadimitriou [204], Papadimitiou [236], and Sipser [279] have good treatments of NP-completeness in the context of complexity theory. Aho, Hopcroft, and Ullman [5] also cover NP-completeness and give several reductions, including a reduction for the vertex-cover problem from the hamiltonian-cycle problem.

The class P was introduced in 1964 by Cobham [64] and, independently, in 1965 by Edmonds [84], who also introduced the class NP and conjectured that P ≠ NP. The notion of NP-completeness was proposed in 1971 by Cook [67], who gave the first NP-completeness proofs for formula satisfiability and 3-CNF satisfiability. Levin [203] independently discovered the notion, giving an NP-completeness proof for a tiling problem. Karp [173] introduced the methodology of reductions in 1972 and demonstrated the rich variety of NP-complete problems. Karp's paper included the original NP-completeness proofs of the clique, vertex-cover, and hamiltonian-cycle problems. Since then, hundreds of problems have been proven to be NP-complete by many researchers. In a talk at a meeting celebrating Karp's 60th birthday in 1995, Papadimitriou remarked, "about 6000 papers each year have the term 'NP-complete' on their title, abstract, or list of keywords. This is more than each of the terms 'compiler,' 'database,' 'expert,' 'neural network,' or 'operating system.'"

Recent work in complexity theory has shed light on the complexity of computing approximate solutions. This work gives a new definition of NP using "probabilistically checkable proofs." This new definition implies that for problems such as clique, vertex cover, traveling-salesman problem with the triangle inequality, and many others, computing good approximate solutions is NP-hard and hence no easier than computing optimal solutions. An introduction to this area can be found in Arora's thesis [19]; a chapter by Arora and Lund in [149]; a survey article by Arora [20]; a book edited by Mayr, Promel, and Steger [214]; and a survey article by Johnson [167].