Theory of Constraint Satisfaction Problems

 

Lecture in Summer Term 2019

 

Content

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.

References

Lecture Notes

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

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

 

Organization

Lecture will be held in english.

Lecturer

Martin Grohe