Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage, den Algorithmus von Zhuk für endliche CSPs anzuwenden.
Literatur: D.Zhuk, A proof of the CSP dichotomy conjecture, https://arxiv.org/abs/1704.01914
Constraint Satisfaction Probleme sind Berechnungsprobleme, bei denen Variablen und Bedingungen gegeben sind, und die Existenz von Werten für die Variablen, welche alle Bedingungen erfüllen, beantwortet werden soll. Bulatov und Zhuk haben 2017 gezeigt, dass, falls die erlaubten Werte aus einer endlichen Menge stammen, solche Probleme immer entweder in polynomieller Zeit lösbar oder NP-vollständig sind. Wir besprechen den Algorithmus von Zhuk, der dieses Resultat impliziert.
Vorträge.
Laufende Beurteilung.
