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

Abstract

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 -- presents itself as the strength of the corresponding De Bruijin-Erdős-type compactness theorem over ZF. More precisely, if $\mathcal{D}$ is a structure, let $K_{\mathcal{D}}$ stand for the following statement: for every structure $\mathcal{X}$ if every finite substructure of $\mathcal{X}$ admits a solution to $\mathcal{D}$, then so does $\mathcal{X}$. We prove that if $\mathcal{D}$ admits no cyclic polymorphism, and thus it is NP-complete by the CSP Dichotomy Theorem, then $K_{\mathcal{D}}$ is equivalent to the Boolean Prime Ideal Theorem (BPI) over ZF. Conversely, we also show that if $\mathcal{D}$ admits a cyclic polymorphism, and thus it is in P, then $K_{\mathcal{D}}$ is strictly weaker than BPI.