DeepRead
Cover of Computers and intractability

Computers and intractability

Michael R. Garey, David S. Johnson · 1979

Programming and computer science › Algorithms and coding interviews

#3,240 most recommended

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

02420082015202020262011 peak · 3
This bookAverage book in Algorithms and coding interviews

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…

    graycat · 2013 · in Discrete Optimization course begins today

  • 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…

    NY_USA_Hacker · 2011 · in What if P = NP?

What Open Library readers say

No Open Library reader has rated it yet.

  • 12 want to read
  • 2 reading
  • 0 have read

Open Library’s page for the book

What Wikipedia says

  • published 1979
  • 338 pages
  • articles in 4 languages

Read the Wikipedia article

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

Explore in the mosaic

Read next: its neighbours on the mosaic