Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...
After successful completion of the course, students will be able to apply recent methods from universal algebra to distinguish those constraint satisfaction problems which are solvable by local consistency methods from those which are not. They will be prepared to follow research talks on constraint satisfaction problems.
Some constraint satisfaction problems can be solved by checking whether the given constraints in an instance are consistent locally, i.e. on subsets of the instance of a fixed bounded size. This implies in particular that they are solvable in polynomial time. We will obtain algebraic characterizations of those constraint satisfaction problems which enjoy this property.
Barto, L., The collapse of the bounded width hierarchy, Journal of Logic and Computation, Volume 26, Issue 3, June 2016, Pages 923–943
Barto, L. and Kozik, M., Constraint Satisfaction Problems solvable by local consistency methods. J. ACM 61, 1, Article 3 (January 2014), 19 pages
