Abstract

The Constraint Satisfaction Problem (CSP) is a type of decision problem with several equivalent formulations. Its original definition was inspired by considerations in Descriptive Complexity, and represents a large part (in some sense) of the class NP. However, any CSP was famously conjectured to be either tractable, or NP-complete, and this was proved independently in 2017 by Bulatov and by Zhuk. I will recall various approaches which were attempted in the quest for the Dichotomy Conjecture, until the methods of Universal Algebra, via polymorphisms of the model, finally bore fruit. Next I will outline Zhuk\s proof of the Dichotomy Conjecture in broad strokes, in particular various types of reductions he used. In the final part I will show the recent result where we proved that just one of the reductions of Zhuk is sufficient to emulate all others and prove the Dichotomy. I will end the lecture explaining why this is not (yet!) a short proof of the Dichotmy, and discuss what our result does show.