Komplexitätstheorie (Sommersemester 2022)

Vorlesung: Prof. Dr. Markus Müller-Olm

Ort und Zeit

Vorlesung: Mo 10:15-12:00 Uhr, M4 und Do 10:15-12:00 Uhr, M4
Übung: Mi 10:15-12:00 Uhr, SRZ 203

Hinweise

Wenn Sie an dieser Veranstaltung teilnehmen möchten, tragen Sie sich bitte bis spätestens 4. April in den Learnwebkurs ein. Bis dahin wird eine Einschreibung ohne Einschreibeschlüssel möglich sein. Danach erfragen Sie bitte den Einschreibeschlüssel per E-Mail bei einem der Veranstalter.
Die erste Vorlesung ist am 4. April 2022 im Hörsaal M4.
Weitere Hinweise zu dieser Veranstaltung finden Sie im Learnwebkurs.

Vorlesungsinhalt

Die Komplexitätstheorie ist ein zentrales Gebiet der (theoretischen) Informatik. Sie beschäftigt sich mit der Frage, welche Mindestresourcen zur Lösung algorithmischer Probleme benötigt werden. Mit der Frage, ob die Klassen P und NP tatächlich, wie von nahezu allen Experten vermutet, verschieden sind, hat die Komplexitätstheorie ein sehr prominentes, auch Nichtexperten bekanntes offenes Problem. Die Vorlesung soll eine Einführung in klassische Techniken und Resultate der Komplexitätstheorie geben und behandelt deshalb Themen wie:

Das Berechnungsmodell und die Klasse P
NP und NP-Vollständigkeit
Hierarchiesätze und Diagonalisierung
Platzkomplexitätsklassen
Die polynomielle Hierarchie und Alternierung
Randomisierte Komplexitätsklassen

Literatur

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Steven Homer and Alan L. Selman, Computability and Complexity Theory, Springer-Verlag, 2013.
Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
Ingo Wegener, Komplexitätstheorie: Grenzen der Effizienz von Algorithmen, Springer-Verlag, 2003.
Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1993