Computers and intractability
by Michael R. Garey, David S. Johnson · first published 1979
45% recommend55% neutral
Why HN recommends it
Concise, approachable guide to NP-completeness, valued as a crash course in theory of computation and for its well-known catalog of hard problems; a go-to reference for working engineers and students of algorithms.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2008–2024Computational complexity
Christos H. Papadimitriou
Recommended by 7 · mentioned by 97 recommend · 9 mention7 recommend · 97 recommend
2018–2020An introduction to formal languages and automata
Peter Linz
Recommended by 4 · mentioned by 54 recommend · 5 mention4 recommend · 54 recommend
2008–2024Theory of computation
Michael Sipser
Recommended by 14 · mentioned by 1914 recommend · 19 mention14 recommend · 1914 recommend
2008–2024Algorithmics
David Harel
Recommended by 11 · mentioned by 1211 recommend · 12 mention11 recommend · 1211 recommend
2008–2025The (new) turing omnibus
A.K. Dewdney
Recommended by 32 · mentioned by 3532 recommend · 35 mention32 recommend · 3532 recommend
2011–2022Classification and regression trees
Leo Breiman
Recommended by 1 · mentioned by 41 recommend · 4 mention1 recommend · 41 recommend
2008–2025Introduction to automata theory, languages, and computation
John E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwani
Recommended by 24 · mentioned by 3324 recommend · 33 mention24 recommend · 3324 recommend
2008–2026Introduction to the theory of computation
Michael Sipser
Recommended by 66 · mentioned by 8966 recommend · 89 mention66 recommend · 8966 recommend
I'm gonna come right out and throw a vote in for two of the canonical works: <i>Computers and Intractability</i> by Garey and Johnson and Donald Knuth's <i>The Art of Computer Programming</i>. The first one is a great, if occasionally thick, crash course in Theory of Computation and…
on “What books should be in a "Personal CS Degree" Reading List?” ↗A related reference, cited by this book, and a bit shorter and simpler is Garey & Johnson Computers and Intractability. It's a really good classic little textbook.
on “Ask HN: What book to read to get a footing in CS theory?” ↗Books I have and recommend: Introduction to the theory of computation - Michael Sipser Computational complexity - Arora, Barak Computational Complexity - Christos H. Papadimitriou Computers and intractability - Michael R. Garey, David S. Johnson
on “Recommended Books on Computational Complexity Theory” ↗…the way of understanding. One exception is Shannon's paper on information theory. In no particular order, here are a list of books I've found exceptional (very much catered to my personal taste): [0] Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnsen [1] The Way of Analysis by Strichartz [2] Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein [3] Fundamental Problems of…
on “Ask HN: Best resources to gain math intuition?” ↗…prequel to SICP, I love The Little Schemer. I love The Art of Prolog too. As a modern successor to Prolog, https://probmods.org/ is awesome. If we talk about theoretical CS, http://en.wikipedia.org/wiki/Computers_and_Intractability is terrific. Very short and elegant.
on “My Top 100 Programming, Computer and Science Books: Part One” ↗Again, the passing of one of CS heroes. /Computers and Intractability/ was one of the first CS books I bought. The anecdote they open with, about coming to your boss claiming "I can't find an efficient algorithm, I guess I'm just too dumb" (as opposed to proving that the…
on “Computational Complexity: David Johnson (1945-2016)” ↗Again, the passing of one of CS heroes. /Computers and Intractability/ was one of the first CS books I bought. The anecdote they open with, about coming to your boss claiming "I can't find an efficient algorithm, I guess I'm just too dumb" (as opposed to proving that the…
on “In Memoriam: David S. Johnson” ↗…solutions will on average cost significantly less than the approximately optimal solutions commonly available now. (3.C) The Cartoon. Early in the reference, Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. and praised in the paper, is a cartoon with an executive sitting behind a desk, a researcher standing…
on “What if P = NP?” ↗…integer linear programming. Actually, it was such problems in network design, and integer linear programming, that got Bell Labs going on the work that resulted in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. which is one of the key books early in the problem P versus NP. It is common now to throw together…
on “Advanced Computer Science Courses” ↗…the $19,900,000 savings and be happy. The claim "we want to show that P = NP so that we can solve all these important problems" has been going on since the cartoon early in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness'. where the mathematician stood before the business executive and admitted that he could not solve the executive's problem but neither could any of the mathematicians…
on “P vs. NP and the Computational Complexity Zoo (2014) [video]” ↗…others and, thus, cause optimization projects to be neglected. The OP is falling into those old traps. Bummer. Such nonsense goes back to the cartoon early in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. where the optimization guy says to the business manager that he (the optimization guy) can't solve the…
on “Discrete Optimization course begins today” ↗…research question of what would be the fastest algorithm in worst case for ILP. This question was asked and explored at Bell Labs and resulted in the now famous Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. So, from there ILP is, yes, in NP-complete. So, now we have at Clay Math in Boston a prize of $1 million…
on “Carnegie Mellon Launches Undergraduate Degree in Artificial Intelligence” ↗…where good means running time that grows no faster than some polynomial in the size of input data for the problem (rough statement -- more details in the famous Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. and more recent sources). IIRC that polynomial criterion came from J. Edmonds. More IIRC, he left…
on “Was a PhD necessary to solve outstanding math problems?” ↗David S. Johnson: http://www.research.att.com/~dsj/ Co-author, with Michael R. Garey (http://cm.bell-labs.com/cm/ms/former/mrg/), of "Computers and Intractability". (See http://citeseer.ist.psu.edu/articles.html .)
on “Failure must always be an option” ↗…communications networks, discovered the role of ILP, encountered the worst case exponential execution time, and got with the theory of NP-completeness and wrote: Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. Here can see the role of the 'satisfiability' (SAT) problem -- it is in NP-complete. Presto! CS,…
on “Milestone for MIT Press’s bestseller, "Introduction to Algorithms"” ↗