Eventos > Seminários de Álgebra

Dualities for constraint satisfaction problems II

23/10/2009 Sexta-feira, 23 de Outubro de 2009, 13h30, Sala B1-01 
Catarina Carvalho (CAUL, Lisboa)

A constraint satisfaction problem for structure B has a duality if the existence of a homomorphism from a given structure A to B is equivalent to the non-existence of a homomorphism to A from a structure belonging to a certain well-behaved class. I will introduce the concepts and the ideas needed to characterize a given type of duality in algebraic, logical and combinatorial languages, and relate it with the complexity of the constraint satisfaction problem.