Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Computers and Intractability
open-in-new
<p><i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i> is a textbook by <a href="/facts/Michael_Garey/xuSLYs90">Michael Garey</a> and <a href="/facts/David_S._Johnson/kGSBxucb">David S. Johnson</a>. It was the first book exclusively on the theory of <a href="/facts/NP-complete/NFPv56DU">NP-completeness</a> and <a href="/facts/Intractability_(complexity)/etHuVF3U">computational intractability</a>. 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 <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a>. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the <a href="/facts/CiteSeer/SceDmd3c">CiteSeer</a> search engine listed the book as the most cited reference in computer science literature. </p>