Computers and Intractability
{{Short description|1979 classic textbook on computational complexity theory}}
{{Infobox book
| name = Computers and Intractability: A Guide to the Theory of NP-Completeness
| title_orig =
| translator =
| image = Garey, Johnson, Intractability, cover.jpg
| caption =
| author = Michael R. Garey and David S. Johnson
| illustrator =
| cover_artist =
| country = United States
| language = English
| series = A Series of Books in the Mathematical Sciences
| subject = Computer science
| genre = Textbook
| publisher = W. H. Freeman and Company
| pub_date = 1979
| media_type = Print
| pages = x+338
| isbn = 0-7167-1045-5
| dewey = 519.4
| congress = QA76.6 .G35
| oclc = 247570676
| preceded_by =
| followed_by =
}}
Computers and Intractability: A Guide to the Theory of NP-Completeness is a textbook by Michael Garey and David S. Johnson.{{cite book|last1=Garey|first1=M. R.|author-link1=Michael R. Garey|last2=Johnson|first2=D. S.|author-link2=David S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|year=1979|isbn=0-7167-1045-5|series=A Series of Books in the Mathematical Sciences|editor=Victor Klee|editor-link=Victor Klee|publisher=W. H. Freeman and Co.|location=San Francisco, Calif.|mr=519066}} 338 pages. [https://archive.org/details/computersintract0000gare Copy] at archive.org
It was the first book exclusively on the theory of NP-completeness and computational intractability.{{cite journal|jstor=2029450|title=Computers and Intractability: A Guide to the Theory of NP-Completeness, book review|author=Juris Hartmanis|pages=90–91|journal=SIAM Review|year=1982|volume=24|issue=1|doi=10.1137/1024022|author-link=Juris Hartmanis}} 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.{{cite web|url=http://citeseer.ist.psu.edu/articles.html|title=Most-cited articles in Computer Science - September 2006 (CiteSeer.Continuity)|access-date=2007-11-03}}
Open problems
Another appendix of the book featured problems for which it was not known whether they were NP-complete or in P (or neither). The problems (with their original names) are:
- Graph isomorphism
- :This problem is known to be in NP, but it is unknown if it is NP-complete.
- Subgraph homeomorphism (for a fixed graph H)
- Graph genus
- Chordal graph completion
- Chromatic indexNP-complete: {{cite journal|last=Holyer|first=Ian|title=The NP-Completeness of Edge-Coloring|journal=SIAM Journal on Computing|volume=10|issue=4|date=November 1981|pages=718–720|doi=10.1137/0210055}}
- Spanning tree parity problemIn P: {{cite book|last=Lovász|first=L.|editor1-last=Lovász|editor1-first=L.|editor2-last=Sós|editor2-first=V.T.|title=Algebraic Methods in Graph Theory, Volume II (Colloquium Szeged, 1978)|publisher=North-Holland|pages=495–517|series=Colloquia Mathematica Societatis János Bolyai, 25}}
- Partial order dimension
- Precedence constrained 3-processor scheduling
- :This problem was still open as of 2016.{{cite conference
|last1=van Bevern
|first1=René
|last2=Bredereck
|first2=Robert
|last3=Bulteau
|first3=Laurent
|last4=Komusiewicz
|first4=Christian
|last5=Talmon
|first5=Nimrod
|last6=Woeginger
|first6=Gerhard J.
|book-title=DOOR 2016: Discrete Optimization and Operations Research
|title=Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
|pages=105–120
|doi=10.1007/978-3-319-44914-2_9
|year=2016
|volume=9869
|series=Lecture Notes in Computer Science
|publisher=Springer-Verlag|arxiv=1605.00901
}}
- Linear programming
- Total unimodularityIn P: {{cite journal|last=Seymour|first=P. D.|title=Decomposition of regular matroids|journal=Journal of Combinatorial Theory, Series B|volume=28|issue=3|date=June 1980|pages=305–359|doi=10.1016/0095-8956(80)90075-1|url=http://dml.cz/bitstream/handle/10338.dmlcz/101946/CzechMathJ_34-1984-2_8.pdf|doi-access=free}}
- Composite number
- :Testing for compositeness is known to be in P, but the complexity of the closely related integer factorization problem remains open.
- Minimum length triangulationIs NP-hard: {{citation | last1 = Mulzer | first1 = Wolfgang | last2 = Rote | first2 = Günter | arxiv = cs.CG/0601002 | at = Art. 11 | doi = 10.1145/1346330.1346336 | issue = 2 | journal = Journal of the ACM | mr = 2417038 | title = Minimum-weight triangulation is NP-hard | volume = 55 | year = 2008}}
- : Problem 12 is known to be NP-hard, but it is unknown if it is in NP.
Reception
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."Ronald V. Book. [https://www.ams.org/journals/bull/1980-03-02/S0273-0979-1980-14848-X/S0273-0979-1980-14848-X.pdf Review: Computers and intractability: A guide to the theory of NP-completeness] Bull. Amer. Math. Soc. (N.S.), 3(2), pp. 898–904, 1980
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".[https://www.jstor.org/stable/2273574 Harry R. Lewis, Review: Computers and intractability: A guide to the theory of NP-completeness], Journal of Symbolic Logic, Vol. 48(2), pp. 498–500, 1983
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."Lance Fortnow, [http://blog.computationalcomplexity.org/2002/08/great-books-computers-and.html 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.