BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Dichotomy Theorem on the computational complexity of the Const
 raint Satisfaction Problem - Petar Markovic (University of Novi Sad)
DTSTART:20251017T130000Z
DTEND:20251017T140000Z
UID:TALK237577@talks.cam.ac.uk
CONTACT:Ioannis Markakis
DESCRIPTION:The Constraint Satisfaction Problem (CSP) is a type of decisio
 n problem with several equivalent formulations. Its original definition wa
 s 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 appro
 aches which were attempted in the quest for the Dichotomy Conjecture\, unt
 il the methods of Universal Algebra\, via polymorphisms of the model\, fi
 nally bore fruit. Next I will outline Zhuk\\s proof of the Dichotomy Conje
 cture 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 jus
 t one of the reductions of Zhuk is sufficient to emulate all others and pr
 ove 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.
LOCATION:SS03\, Computer Laboratory
END:VEVENT
END:VCALENDAR