Inhalt

Die bekannten Komplexitätsklassen P und NP klassifizieren Entscheidungsprobleme. In vielen Fällen ist man aber daran interessiert, _was_ die Lösung ist, und nicht nur ob eine Lösung existiert. In diesem Seminar wollen wir uns anschauen, in welche Komplexitätsklassen man Suchprobleme klassifizieren kann und wann und wie sich die Komplexität von ihren Entscheidungsversionen unterscheiden.
Insbesondere betrachten wir totale Suchprobleme, also Probleme die immer eine Lösung haben die dennoch schwer zu finden ist. Komplexitätsklassen mit denen wir uns beschäftigen werden sind zum Beispiel PLS, PPAD, PPP, CLS/EOPL/PLS geschnitten PPAD und UEOPL.
Die Literatur ist in Englisch, die Vorträge können auf Deutsch oder Englisch sein, abhängig vom Publikum.

Zielgruppe

Master-Studierende der Informatik oder Mathematik

Empfohlene Vorkenntnisse

- Vorlesung "Höhere Algorithmik" oder vergleichbare Veranstaltung

- P, NP und Reduktionen sind bekannt

Literatur

Spezialliteratur aus Zeitschriften