Die Vorlesung Komplexitätstheorie ist als Fortsetzung der Vorlesung Theoretische Informatik II konzipiert. Folgende Themenkreise werden behandelt:

• Komplexitätsklassen NP, PSPACE, P
• Untere Schranken an Laufzeiten
• Schaltkreiskomplexität.

Die Komplexitätstheorie ist als Herzstück der Theoretischen Informatik anzusehen. Solide Kenntnisse dieses Faches erlauben eine fundierte Einordnung der Probleme der Praxis.