Theory of Constraint Satisfaction Problems


Lecture in Summer Term 2016



A constraint satisfaction problem (CSP) asks to assign values to variables subject to certain constraints. CSPs were introduced in the 1970s to model computational problems encountered in image processing. It was quickly realized, however, that constraint satisfaction gives rise to a powerful general framework in which a wide variety of combinatorial problems can be expressed. Today, CSPs are ubiquitous in many different areas of computer science, from artificial intelligence and database systems to circuit design, network optimization, and the theory of programming languages.

It is therefore important to develop efficient algorithms solving CSPs, if not exactly then approximately, and understand their complexity theoretic limitations. Over the last 20 years, a rich theory, with connections to many other branches of theoretical computer science and mathematics, emerged around these questions. The course will be an introduction to this theory.


Lecture Notes

R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.

K.R. Apt. Principles of Constraint Programming. Cambridge University Press, 2003.



Lecture will be held in english.


Martin Grohe


External Links