Komplexitätstheorie B

(Vorlesung mit Übungen, seminarartig ausgestaltet)

Wir wollen in dieser Veranstaltung einige moderne Aspekte der Komplexitätstheorie beleuchten. Dazu werden wir gemeinsam einige neuere Arbeiten zur Komplexität von Problemen durchlesen, insbesondere fokussiert auf Aspekte der Exponentialzeithypothese und der Kernbarkeit bzw. der parameterisierten Komplexität im Allgemeinen.

Teilnahmevoraussetzungen

Kenntnisse, die einem Bachelor-Abschluss in Informatik entsprechen. Kenntnisse aus Komplexitätstheorie A werden nicht vorausgesetzt. Es wäre empfehlenswert, diese Vorlesung parallel zu "Parameterisierte Algorithmen" zu hören.