|
Logik in der Informatik
Prof. Dr. Martin Grohe |
|
In diesem Semester werden wir uns mit deskriptiver Komplexitätstheorie beschäftigen. Die deskriptive Komplexitätstheorie stellt Verbindungen zwischen der Berechnungskomplexität und der sprachlichen Komplexität von algorithmischen Problemen her. Vereinfacht gesprochen sind Probleme, die schwer zu beschreiben sind, auch schwer zu lösen und umgekehrt. So gibt es für die Komplexitätsklasse NP und für die meisten natürlichen Erweiterungen von NP mathematische Logiken, die diese Klassen im obigen Sinn charakterisieren. Die Existenz einer Sprache (Logik), die genau alle in Polynomialzeit berechenbaren Probleme charakterisiert, ist wohl die zentrale offene Frage in der deskriptiven Komplexitätstheorie. In diesem Seminar werden wir neuere Entwicklungen in diesem Bereich anhand aktueller Veröffentlichungen besprechen.
Das Seminar setzt sehr gute und zumindest in einem Bereich auch tiefergehende Kenntnisse der theoretischen Informatik voraus.
Freitags 9-11 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307.