64-656 Vorlesung Komplexitätstheorie

Lehrende:

Marten Maack

Zeit/Ort:

Mo, 12:15 bis 13:45 Uhr, B-201
Mo, 14:15 bis 15:45 Uhr, C-221

Kommentare/ Inhalte:

Die Komplexitätstheorie beschäftigt sich mit den fundamentalen Fragen danach, was für Fragestellungen mit begrenzten Ressourcen algorithmisch lösbar sind und wie Probleme hinsichtlich ihrer algorithmischen Komplexität klassifiziert werden können. Das Modul behandelt fortgeschrittene Themen der Komplexitätstheorie und setzt Grundkenntnissen voraus, die üblicherweise in Vorlesungen über Berechenbarkeit und Komplexität behandelt werden (z.B. Turingmaschinen, die Komplexitätsklassen P und NP, NP-Vollständigkeit). Mögliche Themen umfassen Platzkomplexität, Hierarchiesätze, Komplexität im Zusammenhang mit approximativen, randomisierten und parallelen Algorithmen sowie interaktive Beweissysteme bis hin zum berühmten PCP-Theorem. Es können auch andere Themen, insbesondere aus der aktuellen Forschung im Bereich der Komplexitätstheorie, behandelt werden.

Literatur:

Sanjeev Arora, Boaz Barak: Computational Complexity - A Modern Approach. Cambridge University Press, 2009.
Oded Goldreich: Computational complexity - a conceptual perspective. Cambridge University Press, 2008.
Cristopher Moore, Stephan Mertens: The Nature of Computation. Oxford University Press, 2011.
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Zusätzliche Hinweise zu Prüfungen:

Die Modulprüfung wird voraussichtlich als mündliche Prüfung durchgeführt und umfasst die Inhalte der Vorlesung und Übung. Bei unerwartet hoher Teilnehmerzahl wird stattdessen eine schriftliche Prüfung durchgeführt. Dies wird in der ersten Vorlesung besprochen.