Die Komplexitätstheorie ist ein zentrales Gebiet der (theoretischen) Informatik. Sie beschäftigt sich mit der Frage, welche Mindestressourcen 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 gibt eine Einführung in klassische Techniken und Resultate der Komplexitätstheorie und behandelt deshalb die folgenden Themen:

• 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

Kurs im HIS-LSF