Computers and Intractability

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Computers and Intractability: A Guide to the Theory of NP-Completeness
Author Michael R. Garey and David S. Johnson
Country United States
Language English
Series A Series of Books in the Mathematical Sciences (Victor Klee, ed.)
Subject Computer science
Genre Textbook
Publisher W. H. Freeman and Company
Publication date
1979
Media type Print
Pages x+338
ISBN 0-7167-1045-5
OCLC 247570676
519.4
LC Class QA76.6 .G35

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.[1] It was the first book on the theory of NP-completeness and computational intractability.[2] The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings 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.[3]

Reception[edit]

Soon after it appeared, the book received positive reviews by reputed researchers in the area of theoretical computer science.

In his review, Ronald V. Book recommends the book to "anyone who wishes to learn about the subject of NP-completeness", and he explicitly mentions the "extremely useful" appendix with over 300 NP-hard computational problems. He concludes: "Computer science needs more books like this one."[4]

Harry R. Lewis praises the mathematical prose of the authors: "Garey and Johnson's book is a thorough, clear, and practical exposition of NP-completeness. In many respects it is hard to imagine a better treatment of the subject." Also, he considers the appendix as "unique" and "as a starting point in attempts to show new problems to be NP-complete".[5]

Twenty-three years after the book appeared, Lance Fortnow, editor-in-chief of the scientific journal Transactions on Computational Theory, states: "I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. [...] Garey and Johnson has the best introduction to computational complexity I have ever seen." [6]

References[edit]

  1. ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee, ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 519066. 
  2. ^ Juris Hartmanis (1982). "Computers and Intractability: A Guide to the Theory of NP-Completeness, book review". SIAM Review 24 (1): 90–91. doi:10.1137/1024022. JSTOR 2029450. 
  3. ^ "Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)". Retrieved 2007-11-03. 
  4. ^ Ronald V. Book. Review: Computers and intractability: A guide to the theory of NP-completeness Bull. Amer. Math. Soc. (N.S.), 3(2), pp. 898–904, 1980
  5. ^ Harry R. Lewis, Review: Computers and intractability: A guide to the theory of NP-completeness, The Journal of Symbolic Logic, Vol. 48(2), pp. 498–500, 1983
  6. ^ Lance Fortnow, Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson. Computational complexity blog, August 30, 2002.

See also[edit]