Komplexitätstheorie

Neben der Frage, wie ein Problem algorithmisch gelöst werden kann, ist auch die Frage nach der Effizienz einer solchen algorithmischen Lösung fundamentaler Bestandteil der Informatik. Die Komplexitätstheorie beschäftigt sich mit der Frage, welchen Ressourcenaufwand die Lösung ein Problems erfordert.

Da eine absolute Klassifikation von Problemen sich als sehr schwierig erwiesen hat, ist man zu einer relativen Klassifikation übergegangen. Dabei spielt der Begriff der Reduktion eine zentrale Rolle.

Wir arbeiten insbesondere im Bereich der Circuit Complexity.

Die Veranstaltung gibt einen Einblick in die klassische Komplexitätstheorie. Die aus der Informatik 3 bekannten Begriffe des Rossourcenverbrauchs und der Reduktion werden nochmal motiviert, wiederholt und vertieft.

Der Begriff der Vollständigkeit eines Problems wird am Beispiel von NP nochmals gründlich untersucht und es werden auch für andere Komplexitätsklassen wie P, NL und PSPACE vollständige Probleme vorgestellt. Es werden auch randomisierte Komplexitätsklassen untersucht.

In einem weiteren Kapitel wird die Approximierbarkeit von NP-vollständigen Problemen untersucht.