The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms

Tamás Kátay, László Márton Tóth, Zoltán Vidnyánszky

We study Constraint Satisfaction Problems (CSPs) in an infinite context. We show that the dichotomy between easy and hard problems -- established already in the finite case -- pres…