CSP dichotomy on small structures

Abstract

Given a finite relational structure (template), the fixed-template Constraint Satisfaction Problem asks whether there exists a homomorphism from a similar finite relational structure (which is the input of the problem) into the template. Dichotomy Conjecture about complexity of the Constraint Satisfaction Problem states that each fixed-template Constraint Satisfaction Problem is either tractable or NP-complete (depending on which template is fixed). We review the recent results on the CSP Dichotomy Conjecture which attempt to solve it in small cases. The highlight of our lecture is the result that the Dichotomy Conjecture holds for all templates having at most four elements, but we will also briefly review other recent results on small templates, as well as another application of the main technique used in our proof.