Komplexitätstheorie

Dozent: Prof. Dr. Heribert Vollmer

Frequenz: zweijährlich (ungerade) im Wintersemester

Veranstaltungsart: Vorlesung und Übung (2V + 1Ü + 2S, 7 CP)

Prüfung: mündl. Prüfung

Das Modul vermittelt vertiefte Kenntnisse über Konzepte, Techniken und Phänomenen der Komplexitätstheorie. Nach erfolgreichem Abschluss können die Studierenden algorithmische Probleme hinsichtlich verschiedener Komplexitätsaspekte analysieren. Sie beurteilen Konsequenzen von Vollständigkeitsresultaten. Sie entwickeln Komplexitätsklassifikationen von neuen algorithmischen Problemen.

Gliederung:

• Die Polynomialhzeithierarchie
• Probabilistische Komplexitätsklassen
• Zählklassen
• Der Satz von Toda
• Isomorphie vollständiger Mengen (Berman-Hartmanis-Vermutung)
• Dünne vollständige Mengen und Advice-Klassen (Satz von Karp-Lipton)
• Relativierungen (Satz von Baker-Gill-Solovay)
• Interaktive Beweissysteme

Die Abschlussprüfung des Moduls ist eine mündliche Prüfung.

Termin

Die Prüfungstermine vergeben wir über eine institutsinterne Website (siehe Link unten). Achtung: Dies ersetzt nicht die Anmeldung der Prüfung im QIS.

Anmeldung

Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten).

Studienleistung

Falls Ihre Prüfungsordnung eine Studienleistung für dieses Modul vorsieht, kontaktieren Sie bitte den Dozenten.