Next:10.7
ProblemsUp:10.
Introduction to NPCompletenessPrevious:10.5.1
NPHardness and NPCompleteness
10.6 To Probe Further
This chapter has presented a first level introduction to the notion of
NPcompleteness. 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 NPcompleteness
and also contains a catalogue of NPcomplete problems discovered until
1979.

REF.

M.R. Garey and D.S. Johnson. Computers and Intractability : A Guide to
the Theory of NPcompleteness. 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,
NorthHolland, 1964, pp.2430.
The class P was also independently introduced in 1965 by Edmonds, who also
conjectured P
NP for the first time.

REF.

Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics,
Volume 17, 1965, pp. 449467.
The notion of NPcompleteness was first proposed in 1971 by Stephen Cook
who also gave the first NPcompleteness proof for 3SAT.

REF.

Stephen Cook. The complexity of theorem proving procedures. Proceedings
of the Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151158.
The technique of polynomial reductions was introduced in 1972 by Karp,
who also demonstrated a rich variety of NPcomplete 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. 85103.
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 NPcomplete problems and NPcompleteness proofs.
Next:10.7
ProblemsUp:10.
Introduction to NPCompletenessPrevious:10.5.1
NPHardness and NPCompleteness
eEL,CSA_Dept,IISc,Bangalore