Computers and Intractability
1979 classic textbook on computational complexity theory
- 2 min read
- 2 chapters
Related on Lably
Through Linear programming and Integer factorization
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 index
- Spanning tree parity problem
- Partial order dimension
- Precedence constrained 3-processor scheduling
- This problem was still open as of 2016.
- Linear programming
- Total unimodularity
- 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 triangulation
- Problem 12 is known to be NP-hard, but it is unknown if it is in NP.
Sign in to keep reading
One more chapter is free with a Lably account.
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."
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".
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."