Proseminar Komplexitätstheorie, WS 99/00
Komplexitätstheorie

Veranstaltung: Proseminar, WS 99/00
Professur: Komplexität und Algorithmen
Dozent: Prof. Dr. Torben Hagerup
Zeit und Ort: Di 10-12 Uhr, SR 307
Vorbesprechung: 19. Oktober 1999, 10.15 Uhr, SR 307
Studienabschnitt: Grundstudium
Scheinerwerb: Bei erfolgreichem Vortrag, schriftlicher Ausarbeitung und aktiver Teilnahme
Voraussetzungen: Theoretische Informatik 1 und 2
Inhalt: Das Proseminar beschäftigt sich mit der Komplexitätstheorie, also mit der systematischen Untersuchung von Berechnungsproblemen anhand ihrer inhärenten Schwierigkeit sowie von Maschinenmodellen anhand ihrer Fähigkeit, Berechnungsprobleme innerhalb vorgegebener Ressourcenschranken zu lösen. Das Proseminar soll eine direkte Fortsetzung von Themen bieten, die in der Vorlesung Theoretische Informatik 2 angeschnitten werden.
Literatur: C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.
Vortragsthemen A. Komplexitätsklassen und Hierarchiesätze
B. Die Sätze von Savitch und Immerman-Szelepscényi
C. Reduktionen, Vollständigkeit und der Satz von Fagin
D. coNP und der Satz von Pratt
E. Komplexitätsklassen für Randomisierung
F. Kryptographie
G. Das Verhältnis zwischen P und NP
H. Die polynomielle Hierarchie
I. "Zählende" Komplexitätsklassen
J. Polynomieller Platz: QSAT
K. Polynomieller Platz: IP
L. Noch schwierigere Probleme