Syllabus
1. Definition of CSP, its equivalent forms, basic notions and properties
2. Polymorphisms, algebraic reductions
3. Bounded width problems
4. Schaefer's dichotomy theorem for boolean CSPs
5. Maltsev CSPs
Annotation
The constraint satisfaction problem (CSP) provides a framework in which it is possible to express, in a natural way, many combinatorial problems encountered in artificial intelligence and computer science. In many cases effective algorithms exist to solve such a problem, and in others (such as 3SAT) we can show it to be NP-complete. It is conjectured that every CSP is either in P or NP-complete, which is the so called dichotomy conjecture. In the course, we will study the mathematics of
CSP and focus on algebraic methods.
The course may not be taught every academic year.