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 D is a structure, let KD stand for
the following statement: for every structure X if every finite substructure of X admits
a solution to D, then so does X. We prove that if D admits no cyclic polymorphism,
and thus it is NP-complete by the CSP Dichotomy Theorem, then KD is equivalent to
the Boolean Prime Ideal Theorem (BPI) over ZF. Conversely, we also show that if D
admits a cyclic polymorphism, and thus it is in P, then KD is strictly weaker than
BPI.
