Logic and
Theory of
Discrete Systems

Informatik 7

 

Theory of Constraint Satisfaction Problems

Introduction

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.

Lectures and tutorials will be in English.

Lectures

Time and Place

Monday, 4:15 - 5:45 pm in 2356|054 (5054)

Tuesday, 13:15 - 14:45 in 2356|054 (5054)

(This 3-hour course will be held as 4-hour course, but not every week. The exact dates will be announced in the first lecture.)

 Lecturer

Martin Grohe

Tutorials

Friday, 8:30 - 10:00 am in 2356|055 (5055), held by Daniel Neuen

Exercises

There will be weekly exercise sets. Completing these successfully (at least 50% of possible points) is necessary for admittance to the examination.

Exams

The modalities will be announced later.


References

Lecture Notes

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

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