Computers and Intractability: A Guide to the Theory of NP-Completeness is a computational complexity theory textbook by Michael Garey and David S. Johnson and first published in 1979 by W.H. Freeman and Company. It was the very first book on the theory of NP-completeness and computational intractability.[1] The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later editions of the book). The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature. [2]
