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\H{ o}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.
Categories: math.LO cs.CC