Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage, die mathematischen Methoden für das Studium der Komplexität von Promise Constraint Satisfaction Problemen anzuwenden. Die Studenten sind dann sowohl mit den wesentlichen allgemeinen Reduktionen zwischen Promise Constraint Satisfaction Problemen als auch mit den wichtigsten Algorithmen vertraut.
Promise Constraint Satisfaction Probleme (PCSPs) bieten einen Rahmen für das Studium der Komplexität von Approximation. Bei einem PCSP sind Variablen und Bedingungen gegeben, wobei es von letzteren eine "strenge" und eine "nicht-strenge" Version gibt; das Ziel ist es, Instanzen, bei denen die strengen Bedingungen erfüllbar sind, von solchen zu unterscheiden, bei denen nicht einmal die nicht-strengen Bedingungen erfüllbar sind. Ein konkretes PCSP, dessen Komplexität ein bekanntes offenes Problem ist, ist das Problem, 3-färbbare Graphen von Graphen, welche nicht einmal 10-färbbar sind, zu unterscheiden. Wir werden Methoden aus der universellen Algebra sowie der algebraischen Topologie behandeln, welche es ermöglichen, die Komplexität von PCSPs zu klassifizieren.
Vorträge
Literatur: L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, Journal of the ACM 68/4 (2021), 1-66. https://arxiv.org/abs/1811.00970
Laufende Beurteilung.
Nicht erforderlich
Logik und/oder Algebra I
