- Introduction to the Theory of Computation, by M. Sipser
- Computational Complexity, by C. H. Papadimitriou
- Handbook of Computer Science, vol A, the article by David Johnson.
- Computers and Intractability: A guide to the theory of NP-Completeness, by M. R. Garey and D. S. Johnson.
- Structural Complexity I, by J. L. Balcazar, J. Diaz, and J, Gabarro
- Models of Computation by John E. Savage

Daniel A. Spielman Last modified: Mon Jan 25 13:31:35 1999