The Constraint Satisfaction Problem (CSP) models general search problems, where the goal is to find a solution that satisfies all given constraints. Due to its generality, constraint solving has multiple applications in computer science: examples include reasoning, scheduling and planning in artificial intelligence, query evaluation in databases, or optimization in operations research.
In this course, we focus on the theory of solving CSPs. We will learn about general purpose techniques from constraint programming such as constraint propagation and search strategies and discuss algorithmic approaches tailored towards specific types of constraints and restricted classes of instances.
The algorithmic part of this course is complemented by an in-depth complexity theoretic analysis of constraint solving. While the CSP is NP-complete in general, our goal is to understand on which classes of instances constraint solving becomes tractable and when it remains hard. |
