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
Literaturhinweise
Spezialliteratur aus Zeitschriften
13 Termine
Regelmäßige Termine der Lehrveranstaltung
Do, 18.04.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 25.04.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 02.05.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 16.05.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 23.05.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 30.05.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 06.06.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 13.06.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 20.06.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 27.06.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 04.07.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 11.07.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)
Do, 18.07.2024 14:00 - 16:00
Seminar über Komplexitätstheorie
Dozenten:
Michaela Krüger
Räume:
T9/SR 006 Seminarraum (Takustr. 9)