Inhalt
Die Komplexitätstheorie klassifiziert Berechnungsprobleme gemäss algorithmischen Ressourcen wie Berechnungszeit oder Speicherplatz, die zu ihrer Lösung benötigt werden. Ziel ist ein theoretisches Verständnis davon welche Berechnungsprobleme effiziente Algorithmen erlauben und welche nicht. Eine zentrale Rolle spielt die Klasse P der in polynomieller Zeit lösbaren Berechnungsprobleme. Das zentrale Problem ist das P versus NP Problem, eines der Millenniumsprobleme der Mathematik, und Smale zufolge eines der drei grössten offenen Probleme der Mathematik. Die Vorlesung bietet eine Einführung in dieses Problem und die es umgebende Theorie.
Auf StudIP findet sich ein wöchentlich aktualisiertes Skript des aktuellen Standes.
Vorlesungen
Dienstag 12:00-14:00 IM SR030
Mittwoch 10:00-12:00 IM HS12
Übungen von Johannes Heil
Donnerstag 10:00-12:00 JUR SR154
Literatur
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Das Oberseminar ist eine gemeinsame Veranstaltung mit Tobias Kaiser. Es beinhaltet Forschungsvorträge der Arbeitsgruppen und ihrer Gäste. Fortgeschrittene Studierende, die ihr Wissen in mathematischer Logik und/oder Komplexitätstheorie vertiefen wollen, können hier über ein gemeinsam gewähltes und gemeinsam erarbeitetes Thema vortragen.
Programm pdf
