| Kommentar |
Die Komplexitätstheorie beschäftigt sich mit der Frage, welcher Aufwand, etwa an Rechenzeit oder Speicherplatz, erforderlich ist, um bestimmte algorithmische Probleme zu lösen. Dieses Modul ist eine Einführung in die Themen und Methoden der Komplexitätstheorie. Im Mittelpunkt stehen dabei die grundlegenden Zeit- und Platzkomplexitätsklassen.
Konkrete Inhalte des Moduls sind: Hierarchiesätze, NP-Vollständigkeit und die P vs NP-Frage, Orakelmodelle und die polynomielle Hierarchie, deskriptive Komplexität und der Satz von Fagin, Platzkomplexität und der Satz von Savitch, die Klassen L, NL und PSPACE. |
