A constraint satisfaction problem (CSP) is a computational problem is the problem of deciding whether a given set of constraints admits a solution in a given set. Common examples are the problem of solving systems of linear equations over the real numbers, or the problem of determining whether a propositional boolean formula admits a solution.

In this course, we will introduce the mathematical theory hiding behind CSPs and show how symmetries can be used to obtain a classification of the CSPs that can be solved efficiently.

• Lecturer: Prof. Dr. Antoine Mottet
• Summer semesters
• Bachelor students in Technomathematik, Master students in Technomathematik, Master students in Computer Science
• 6 ECTS
• 2 meetings per week (1.5 hour lectures, 1.5 hour tutorials)

There are no formal prerequisites to register to this course. However, students are expected to have some basic knowledge in discrete mathematics, linear algebra, and some familiarity with the complexity classes P and NP.

• Constraint satisfaction problems
• Relational structures and homomorphisms
• Primitive positive logic, primitive positive interpretations
• Universal algebra, clones, Galois correspondence
• Local consistency methods
• Complexity dichotomy