Personal tools
You are here: Home Events Abstract Archives 2001 The complexity of constraint satisfaction: an algebraic approach

The complexity of constraint satisfaction: an algebraic approach

Andrei Krokhin Oxford University 4pm Tuesday 23 October Room 2511, JCMB, King's Buildings

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.

Document Actions