19306711 Seminar

SoSe 24: 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

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)

Studienfächer A-Z