''Computers and Intractability: A Guide to the Theory of NP-Completeness'' is a textbook by
Michael Garey
Michael Randolph Garey (born November 19, 1945) is a computer science researcher, and co-author (with David S. Johnson) of '' Computers and Intractability: A Guide to the Theory of NP-completeness''. He and Johnson received the 1979 Frederick W ...
and
David S. Johnson
David Stifler Johnson (December 9, 1945 – March 8, 2016) was an American computer scientist specializing in algorithms and optimization. He was the head of the Algorithms and Optimization Department of AT&T Labs Research from 1988 to 2013, an ...
.
It was the first book exclusively on the theory of
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
ness and
computational intractability. 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
CiteSeerX (formerly called CiteSeer) is a public search engine and digital library for scientific and academic papers, primarily in the fields of computer and information science.
CiteSeer's goal is to improve the dissemination and access of ac ...
search engine listed the book as the most cited reference in computer science literature.
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
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H''
: f \colon V(G) \to V(H)
such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...
#: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
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
#
Chordal graph completion
#
Chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
# Spanning tree parity problem
#
Partial order dimension
# Precedence constrained 3-processor scheduling
#:This problem was still open as of 2016.
#
Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
# Total unimodularity
#
Composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
#:Testing for compositeness is known to be in P, but the complexity of the closely related
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
problem remains open.
#
Minimum length triangulation
#: 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
Ronald Vernon Book (March 5 1937 – May 28, 1997 in Santa Barbara, California) was a theoretical computer scientist. He published more than 150 papers in scientific journals.
His papers are of great impact for computational complexity theory
In ...
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
Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology.
Biogra ...
, editor-in-chief of the
scientific journal
In academic publishing, a scientific journal is a periodical publication intended to further the progress of science, usually by reporting new research.
Content
Articles in scientific journals are mostly written by active scientists such as s ...
''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
Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology.
Biogra ...
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
*
List of NP-complete problems
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . ...
*
References
{{Reflist
Computer science books
1979 non-fiction books