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
- Skript
- Semesterapparat
- 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.
- 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.
Dozent
Vorlesungszeiten
Dienstag 10:00 - 12:00 in O27/122
Donnerstag 10:00 - 12:00 in O27/122
Übungsleiter
Prof. Dr. Jacobo Torán