''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."

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.

References

{{Reflist Computer science books 1979 non-fiction books

Open problems

Reception

See also

References