Skip to main content

Constraint Satisfaction Problems

Computational problems from many different application areas can be seen as constraint satisfaction problems. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be seen in this way. In any constraint satisfaction problem there is a collection of variables which all have to be assigned values, subject to specified constraints. An equivalent way of definining constraint satisfaction problems is via homomorphisms between relational structures. Our goal is to understand the computational complexity of constraint satisfaction problems.

Head of Activity




Past Members

Selected Publications

View All