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 zum einen 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
- Lehrende/r: Jens Oliver Gutsfeld
- Lehrende/r: Sebastian Kenter
- Lehrende/r: Markus Müller-Olm
- Lehrende/r: Christoph Ohrem
Semester: SoSe 2020