Description
"Title: Introduction to the world of CSPs
Abstract:
The Constraint Satisfaction Problem, or CSP for short, over a relational structure B (called the template structure) is the decision problem where we are given a finite structure A with the same signature as B and we need to decide whether there exists a homomorphism from A to B. According to the famous result of Bulatov and Zhuk we know that CSPs over finite template structures exhibit a complexity dichotomy: they are all in P or NP-complete. Following this result, it is natural to ask when and how this dichotomy can be generalized for infinite template structures. A currently standing conjecture in this direction is due to Bodirsky and Pinsker which states that the same complexity dichotomy holds for first-order reducts of finitely bounded homogeneous structures.
In my talk I will give a brief introduction to some of the main techniques and results used in the study of CSPs putting a special emphasis on the ones with infinite templates. In this endeavour I might touch on some topics in model theory as well."