Seminar über Komplexitätstheorie
Michaela Krüger
Kommentar
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
Schließen
Literaturhinweise
Spezialliteratur aus Zeitschriften
13 Termine
Regelmäßige Termine der Lehrveranstaltung
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 ... Lesen Sie weiter