
Computers and intractability
Michael R. Garey, David S. Johnson · 1979
Programming and computer science › Algorithms and coding interviews
#3,240 most recommended
Hacker News
20
mentions by 11 people · top 17% of 15,732 books
Open Library
—
No ratings yet
12 want to read
Wikipedia
438
article views a month
About the book
A guide to the theory of NP-completeness, the part of computational complexity that classifies problems by how hard they are to solve exactly. It is written by Michael R. Garey with David S. Johnson, and covers the formal framework (Turing machines, polynomial-time reductions) together with an appendix catalog of hundreds of NP-complete problems from graph theory, scheduling, logic, sets, and number theory. The central point is that many practically important computational problems are NP-complete, so no efficient exact algorithm is known for them and none is likely to exist unless P equals NP. The book's method for establishing this is to show a problem is at least as hard as a known NP-complete problem by means of a polynomial-time reduction. It then argues that a researcher or engineer who recognizes this status should stop searching for an exact polynomial algorithm and turn instead to approximation, heuristics, special cases, or pseudo-polynomial methods.
Written by Claude from what it knows of this book.
What Hacker News says 45% recommend · 0% critical
In the commenters’ own words
Part II There had been another place I'd saved the company from going out of business: Our two representatives from Board Member General Dynamics (GD) had…
Okay, the question of P versus NP is important. Now keep in mind that I admitted this when read the rest below: Contention: In this research question of P…
What Open Library readers say
No Open Library reader has rated it yet.
- 12 want to read
- 2 reading
- 0 have read
What Wikipedia says
- published 1979
- 338 pages
- articles in 4 languages
Reddit communities — coming later
The threads it came up in
Details
- First published
- 1979
- ISBN
- 9780716710455
- Editions known
- 4 at Open Library
- Open Library
- OL6801337W
519.4AlgorithmsComputational complexityComputer algorithmsComputer programmingComputer science, mathematicsQa76.6 .g35
Read next: its neighbours on the mosaic
Computational complexityChristos H. Papadimitriou · 1994 · recommended by 7 people · similar by subject and what people say about it
ComputationMarvin Minsky · 1967 · recommended by 5 people · similar by subject and what people say about it
Introduction to the theory of computationMichael Sipser · 1997 · recommended by 66 people · similar by subject and what people say about it
Probability and ComputingMichael Mitzenmacher · 2005 · recommended by 4 people · similar by subject and what people say about it
Data structures and algorithmsAlfred V. Aho · 1983 · recommended by 1 person · similar by subject and what people say about it
The art of computer programmingDonald Knuth · 1968 · recommended by 336 people · similar by subject and what people say about it
The Philosopher's ToolkitJulian Baggini · 2002 · recommended by 8 people · 2 people recommended both
GeneratingfunctionologyHerbert S. Wilf · 2005 · recommended by 9 people · loosely similar by subject
Introduction to AlgorithmsThomas H. Cormen · 1990 · recommended by 274 people · named together in 2 comments
Introduction to automata theory, languages, and computationJohn E. Hopcroft · 1979 · recommended by 24 people · similar by subject and what people say about it
Theory of computationMichael Sipser · 2007 · recommended by 14 people · similar by subject and what people say about it
Computability and complexityNeil D. Jones · 1997 · recommended by 1 person · similar by subject and what people say about it
Computational complexitySanjeev Arora · 2007 · recommended by 3 people · similar by subject and what people say about it
The nature of computationCristopher Moore · 2009 · recommended by 10 people · similar by subject and what people say about it
The Practice of ProgrammingBrian W. Kernighan · 1999 · recommended by 90 people · similar by subject and what people say about it
From Frege to GödelJean van Heijenoort · 1967 · recommended by 3 people · loosely similar by subject
The (new) turing omnibusA.K. Dewdney · 1993 · recommended by 32 people · similar by subject and what people say about it
The way of analysisRobert S. Strichartz · 1995 · recommended by 3 people · loosely similar by subject
Computability and logicGeorge Boolos · 1974 · recommended by 7 people · similar by subject and what people say about it
Art of Programming - Volume 3 - Answers to ExercisesDonald Knuth · recommended by 6 people · similar by subject and what people say about it
Sorting and searchingDonald Knuth · 1973 · recommended by 10 people · similar by subject and what people say about it
Computer systemsRandal Bryant · 2002 · recommended by 67 people · similar by subject and what people say about it
Programming PearlsJon Bentley · 1999 · recommended by 158 people · similar by subject and what people say about it
Concrete mathematicsRonald L. Graham · 1988 · recommended by 140 people · similar by subject and what people say about it