---
title: "Computers and Intractability: A Guide to the Theory of NP-Completeness"
authors:
  - Michael R. Garey
  - David S. Johnson
year: 1979
venue: W. H. Freeman
arxiv: null
doi: null
source: "https://archive.org/details/computersintract0000gare"
topics:
  - complexity
  - garey-johnson
  - np-completeness
seed_rank: 727
seed_batch: perfects-algorithms-2026-08-13
reviewed: 2026-08-13
pool: maths-foundations
relevance_score: 10
lineage: algorithms-and-complexity
cites:
  - title: The Complexity of Theorem-Proving Procedures
    url: "https://doi.org/10.1145/800157.805047"
    year: 1971
    arxiv: null
    doi: 10.1145/800157.805047
  - title: Reducibility Among Combinatorial Problems
    url: "https://doi.org/10.1007/978-1-4684-2001-2_9"
    year: 1972
    arxiv: null
    doi: 10.1007/978-1-4684-2001-2_9
see:
  - "724-the-complexity-of-theorem-proving-procedures"
  - "725-reducibility-among-combinatorial-problems"
---

# Computers and Intractability: A Guide to the Theory of NP-Completeness

## One-sentence takeaway

Garey & Johnson is the field guide to NP-completeness: reduction patterns, a huge problem catalogue, and the famous open-problem appendix.

## Why it matters here

Still the first book to pull when a Broadside or engine combinatorial bottleneck looks hard. Classify the problem against the catalogue, then decide whether to SAT-encode, approximate, or restrict — don’t reinvent Karp’s list.

## Key ideas

- Standard reduction patterns (restriction, local replacement, component design) are taught as a craft.
- The appendix catalogues hundreds of NP-complete problems by domain (graphs, scheduling, storage, games).
- Advice on coping with intractability — special cases, approximation, exponential algorithms — is part of the book, not an afterthought.
- Cook and Karp are the cited founding papers; later PCP/approximation theory is outside its 1979 scope.
- W. H. Freeman, San Francisco, 1979 (ISBN 0-7167-1044-7 / 0-7167-1045-5); x+338 pages.

## Caveats

## Links

- Internet Archive: https://archive.org/details/computersintract0000gare
- WorldCat: https://search.worldcat.org/title/Computers-and-intractability-%3A-a-guide-to-the-theory-of-NP-completeness/oclc/4195125