Die Vorlesung folgt nicht einem einzelnen Buch. Die folgende Literatur ist zu empfehlen.

  • Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
  • Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press. Eine Vorabversion ist (immer noch) verfügbar unter: http://theory.cs.princeton.edu/complexity/book.pdf
  • Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
  • Kozen. Theory of Computation. Springer. 2006.
  • Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. New York. 1994.