10.6 To Probe Further

This chapter has presented a first level introduction to the notion of NP-completeness. We have consciously avoided a technical discussion of the topics since that would be the subject of a more advanced course. For a rigorous treatment of the subject, you should consult the following references.

The following book is a classic source on the theory of NP-completeness and also contains a catalogue of NP-complete problems discovered until 1979.

REF.

M.R. Garey and D.S. Johnson. Computers and Intractability : A Guide to the Theory of NP-completeness. W.H. Freeman, 1979.

The class P was first introduced by Cobham in 1964,

REF.

Alan Cobham. The intrinsic computational difficulty of functions. Proceedings of the 1964 Congress for Logic, Methodology, and Philosophy of Sciences, North-Holland, 1964, pp.24-30.

The class P was also independently introduced in 1965 by Edmonds, who also conjectured P$\not=$ NP for the first time.

REF.

Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, Volume 17, 1965, pp. 449-467.

The notion of NP-completeness was first proposed in 1971 by Stephen Cook who also gave the first NP-completeness proof for 3-SAT.

REF.

Stephen Cook. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151-158.

The technique of polynomial reductions was introduced in 1972 by Karp, who also demonstrated a rich variety of NP-complete problems.

REF.

Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, edited by R.E. Miller and J.W Thather, Plenum Press, 1972 pp. 85-103.

This chapter has liberally drawn from the material presented in two books: Chapter 36 of the book by Cormen, Leiserson, and Rivest and Chapter 13 of the book by Sara Baase and Allen Van Gelder. These two books are a rich source of NP-complete problems and NP-completeness proofs.