Institut für Abwasserwirtschaft und Gewässerschutz

This course gives an introduction to the topic of constraint satisfaction problems and their complexity. A constraint satisfaction problem (CSP) is a computational problem of the form "Given variables and constraints on the variables, does there exist an assignment of the variables to some concrete domain that satisfies all the constraints?" The framework of CSPs is very general, and in fact every computational problem is equivalent to a CSP. The study of CSPs has been very prolific in the past, both in practice (e.g., with SAT solvers) and in complexity theory, a prominent field of theoretical computer science.

In this course, we will review the theoretical aspects of CSPs. The course will cover the basics of the theory such as the universal-algebraic approach to constraint satisfaction and several classical algorithms such as local consistency checking and the Bulatov-Dalmau algorithm.

Basic knowledge in predicate logic and an affinity to abstract mathematical thinking are highly recommended in order to follow this course.