Further Reading: Introduction to Complexity Theory

Annotated pointers for going deeper into P, NP, reductions, and the great open problem. Start with the textbook treatments to firm up the definitions, then branch toward the survey writing, the original sources, and the practical solvers — whichever pulls you. Every item below is a real, verifiable work (Tier 1) or a clearly attributed standard result (Tier 2).

Core textbook treatments

Sipser, Introduction to the Theory of Computation (3rd ed.), Chapters 7–8 The canonical undergraduate treatment of P, NP, NP-completeness, and the full Cook–Levin proof we only sketched in §37.4. If you want to see the Boolean-formula encoding of a Turing-machine computation done in loving, careful detail, this is the place — readable and rigorous. The natural next book after this chapter.

Rosen, Discrete Mathematics and Its Applications (8th ed.), §3.3 and §11 (complexity of problems) The market-standard discrete-math presentation, at this chapter's level. Good for extra drill on classifying problems and for the tractable/intractable framing carried over from Chapter 14.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042) Freely available. The CS-flavored companion to this whole book; its treatment of how reductions transfer hardness pairs well with §37.4. Strong on the "why a programmer cares" framing.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapter 34 ("NP-Completeness") and Chapter 35 ("Approximation Algorithms") The algorithms-textbook view: Chapter 34 gives polished versions of the classic reductions (including CLIQUE, VERTEX COVER, Hamilton, TSP), and Chapter 35 develops the "give up exact" row of the coping menu (§37.6) — approximation algorithms with provable ratios, including the metric-TSP results referenced in Chapter 30.

The classic specialist references

Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979) The legendary field guide to NP-completeness. Its appendix is a vast catalog of NP-complete problems — the "zoo" of §37.5 in its full, encyclopedic form — and its early chapters are still one of the clearest accounts of how to use reductions in practice. The book that made NP-completeness a working tool for a generation of computer scientists.

Arora & Barak, Computational Complexity: A Modern Approach (Cambridge, 2009) The graduate-level standard, for after Sipser. This is where to read about the landscape beyond P and NP mentioned in the Deep Dive: co-NP, the polynomial hierarchy, PSPACE, randomized classes, and the "barriers" results explaining why P vs. NP resists the natural proof strategies (§37.6).

The original sources (history)

Cook, "The Complexity of Theorem-Proving Procedures" (Proc. 3rd ACM STOC, 1971) Tier 2 — the foundational paper, cited for its historical role. Stephen Cook's original proof that SAT is NP-complete — the Cook–Levin theorem of §37.4. Leonid Levin proved an equivalent result independently in the USSR around the same time; the joint name honors both. Worth reading the introduction even if the full proof is dense.

Karp, "Reducibility Among Combinatorial Problems" (in Complexity of Computer Computations, 1972) Tier 2 — the paper that launched the zoo. Richard Karp's demonstration that 21 classic problems are NP-complete by reduction from SAT — the avalanche described in the §37.5 Threshold Concept. Reading the list and the reduction sketches is the best way to internalize "one hardness, many costumes."

Surveys and essays (for perspective)

Aaronson, "P =? NP" (survey, in Open Problems in Mathematics, Springer, 2016; also on the author's site) Freely available. A long, witty, deep survey of everything around P vs. NP — what it means, why it's hard, what a proof might look like, and why the question matters beyond computer science. The source of this chapter's epigraph; the single best "where does this all lead?" read.

Fortnow, "The Status of the P versus NP Problem" (Communications of the ACM, vol. 52 no. 9, 2009) Tier 2 — a widely read, citable survey. A compact, accessible account of the problem's stakes, the main approaches, and the obstacles, by a leading complexity theorist. Good if the Aaronson survey is more than you want right now.

Clay Mathematics Institute, "P vs NP Problem" (official problem statement, claymath.org) Freely available. The formal Millennium Prize Problem description (§37.6) and Stephen Cook's official problem statement for the institute. Read it to see the question posed with full precision and to confirm the \$1,000,000 is real.

On the practical side: SAT solvers

Biere, Heule, van Maaren & Walsh (eds.), Handbook of Satisfiability (2nd ed., IOS Press, 2021) The reference for the §37.6 "give up fast" lesson: how industrial CDCL SAT solvers dispatch formulas with millions of variables despite SAT's NP-completeness. Dense, but the introductory chapters explain why worst-case hardness and practical solvability coexist.

The SAT Competition (satcompetition.org) Freely available. The annual benchmark where modern SAT solvers compete on enormous real-world instances. Browsing recent results makes §37.6's claim — that "NP-complete" bounds the worst case, not your case — concrete and current.

Suggested order

  1. Re-read §§37.2–37.4 here, then read Sipser Ch. 7 for the definitions and Ch. 8 / the Cook–Levin proof to see the keystone proved in full.
  2. Read Karp's 1972 paper (skim the reductions) to feel the zoo expand, with Garey & Johnson's early chapters as a companion on reduction technique.
  3. Read the Aaronson survey (or the shorter Fortnow CACM article) for the big-picture stakes; glance at the Clay problem statement.
  4. For the practical payoff, skim the Handbook of Satisfiability introduction and the SAT Competition results.
  5. Save Arora & Barak for after you've met more theory — it is the gateway to co-NP, PSPACE, and the polynomial hierarchy of the Deep Dive path.