Constraint satisfaction problems and dualities
Seminar Room 1, Newton Institute
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.