- Steve Cook, The Complexity of Theorem-Proving Procedure
- Defined the P v NP problem and showed SAT is NP-complete
- Richard Karp, Reducibility Among Combinatorial Problems
- Shows 21 combinatorial problems NP-complete
- Michael Garey and David Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness
- The reference for NP-completeness. Every computer scientist should own this book.