WHY MY RELATIONS ARE DIFFICULT
Dr Dave Cohen, Department of Computer Science, Royal Holloway, University of London

Abstract: Many applications in AI involve searching over a very large possibility space. Constraint satisfaction is a general problem solving paradigm that expresses some of these search problems in a natural way.

The constraint satisfaction paradigm consists of defining a problem in terms of variables which need to be assigned suitable values. Certain subsets of these variables are then constrained by restricting the simultaneous values they may be assigned.

In general the constraint satisfaction problem is NP-hard but there are well known restrictions to the hypergraph of constraint interactions (structure) or to the allowable relations of constraint restrictions (language) that make the problem tractable (solvable in polynomial time). The tradeoff here is expressiveness for tractability.

In this talk we introduce the constraint satisfaction paradigm and briefly describe expressiveness and tractability. We then introduce an algebraic framework for describing language based tractability, and discuss some of the known results. Lastly we derive a general technique for developing new, more expressive, tractable constraint languages from existing examples.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 20 November 2001.

back