Komplexitätstheorie

Informationen

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

Literatur

  • 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.
  • B. Moret, The Theory of Computation. Addison Wesley 1998.
  • 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.
  • G. Wechsung, Vorlesungen zur Komplexitätstheorie. Teubner 2000.
  • I. Wegener, Komplexitätstheorie. Springer 2003.

Vorlesungszeiten

Dienstag 10:00 - 12:00 in O27/122
Donnerstag 10:00 - 12:00 in O27/123

Übungsleiter

Prof. Dr. Jacobo Torán

Weitere Informationen

LSF-Eintrag