4pm Tuesday 23 October
Room 2511, JCMB, King's Buildings
Abstract
Many combinatorial problems such as
Satisfiability from propositional logic and Graph Colorability
can be expressed as "constraint satisfaction problems"
using appropriate "constraint language", that is,
a set of relations over some fixed finite set of values.
It is well-known that there is a trade-off between the expressive power
of a constraint language and the complexity of the problems it
can express. In this talk we will show that algebraic invariance
properties of relations provide
a natural (and very useful) tool in classifying the complexity
of constraint satisfaction problems.
Martin Grohe
Tuesday 9 October 2001
An error occured whilst processing this directive