For background material, I suggest consulting one of the following. Be aware that each of them might use different notation.
Sipser, M. Introduction to the Theory of Computation. 1st ed. Florence, KY: Thomson/Brooks Cole, 1996. ISBN: 053494728X.
Papadimitriou, C. H.Computational Complexity. 1st ed. Boston: Addison Wesley Publishing Company, 1994. ISBN: 0201530821.
Handbook of Computer Science. Vol. A. Cambridge, MA: MIT Press, 1994. ISBN: 0262720140. The article by David Johnson.
Garey, M. R., and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979. ASIN: 0716710447.
Balcazar, J. L., J. Diaz, and J. Gabarro. Structural Complexity I. Berlin, New York: Springer Verlag, 1988. ASIN: 0387186220.
Savage, John E. Models of Computation. Boston: Pearson Education POD, 1997. ISBN: 0201895390.