  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.
