The Dichotomy Theorem on the computational complexity of the Constraint Satisfaction Problem

Add to your list(s) Download to your calendar using vCal

• Petar Markovic (University of Novi Sad)
• Friday 17 October 2025, 14:00-15:00
• SS03, Computer Laboratory.

If you have a question about this talk, please contact Ioannis Markakis.

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.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• Martin's interesting talks
• SS03, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list
• yk449

Note that ex-directory lists are not shown.