Tutorial: Constraint Satisfaction Problem over a Fixed Template

The constraint satisfaction problem (CSP) provides a common framework for expressing a wide range of both theoretical and real-life combinatorial problems. One solves an instance of CSP by assigning values to the variables so that the constraints are satisfied. This tutorial will concentrate on the computational (and descriptive) complexity of CSP over a fixed constraint language on a finite domain. This restricted framework is still broad enough to include many NP-complete problems, yet it is narrow enough to potentially allow a complete classification of all such CSP problems. One particularly important achievement is the understanding of what makes a problem in the class computationally easy or hard. It is not surprising that hardness comes from lack of symmetry. However, usual objects capturing symmetry, automorphisms (or endomorphisms) and their groups (or semigroups), are not sufficient in this context. It turned out that the complexity of CSP is determined by more general symmetries: polymorphisms and their clones. My aim in this tutorial is to introduce the basics of this exciting area and highlight selected deeper results. . 12: 30 14: 30 Lunch

Authors

• Libor Barto

Keywords

No keywords are indexed for this paper.