An Isaac Newton Institute Programme

Logic and Algorithms

Constraint satisfaction problems and dualities

6th March 2006

Author: Andrei Krokhin (Durham)

Abstract

We consider constraint satisfaction (or homomorphism) problems of the form CSP(B): given a structure A, is there a homomorphism from A to a fixed structure B? The concept of duality for CSPs is based on the idea of providing an obstruction set (of structures) for homomorphism to B. There exist several types of duality according to the properties of obstruction sets. In this talk, we will review three main types of duality and discuss the problem of characterising structures with a given type of duality.