Logic Seminar

For a given finite relational structure R, the associated constraint satisfaction problem (or CSP) is the problem of testing when a structure admits a homomorphism into R. The algebraic approach studies a CSP by considering its algebra of so-called polymorphisms, operations (of all arities) which preserve the relations in R. This approach has led to many classification results. For instance, CSPs solvable by polynomial time algorithms, linear relaxation, and constraint propagation have all been classified. In this talk I will present partial results towards similar classifications of Borel CSPs with various descriptive set theoretic properties: those problems which are Π11 in the codes, effectivizable, or equivalent to their classical version.