For background material, I suggest consulting one of the following.
Be aware that each of them might use different notation.
- 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