• Inhalte:
  • Platz- und Zeitkomplexität
  • Komplexitätsklassen
  • Vollständige Probleme
  • Das P-NP-Problem
  • Komplexitätstheoretische Begründung der Zufälligkeit
  • Interaktive Beweissysteme
• Skript
• Semesterapparat
• Weiterführende Links:
  Complexity Zoo

S. Arora und B. Barak, Computational Complexity: A Modern Approach. Cambridge U. Press 2009
L. Hemaspaandra und M. Ogihara, The Complexity Theory Companion. Springer 2002. 
J. Köbler, U. Schöning und J. Torán, The Graph Isomorphism Problem. Birkhauser 1993. 
C. Papadimitriou, Computional Complexity. Addison Wesley 1994. 
U. Schöning, Perlen der Theoretischen Informatik. Wissenschaftsverlag, 1995. 
M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, 1997.