G. Wechsung: Vorlesungen zur Komplexitätstheorie. Teubner, Stuttgart 2000.
K.R.Reischuk: Komplexitätstheorie. Teubner, Stuttgart 1999.
K.Wagner, G.Wechsung: Computational Complexity. Deutscher Verlag der Wissenschaften, Berlin 1986.
I. Wegener: Komplexitätstheorie. Springer, Berlin 2003.
J.L.Balcazar, J.Diaz, J.Gabarro: Structural Complexity I. Springer-Verlag, Berlin 1988.
M.R.Garey, D.S.Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, San Francisco 1979.
J.E.Hopcroft, J.D.Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Oldenbourg 2000.
J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, seit 1979.
J.E.Hopcroft, R. Motwani, J.D.Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Pearson Studium 2006. (auch in engl.)