Title: The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms Show Chinese title

Title: CSP二分法，选择公理和循环多项式

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\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. Show Chinese abstract

Abstract: 我们研究无限情境下的约束满足问题（CSPs）。 我们证明了在有限情况下已经确立的容易与困难问题之间的二分法，在ZF系统中对应德布鲁因-埃尔斯定理的紧性定理强度下显现出来。 更准确地说，如果$\mathcal{D}$是一个结构，令$K_\mathcal{D}$表示以下陈述：对于每个结构$\mathcal{X}$，如果$\mathcal{X}$的每个有限子结构都对$\mathcal{D}$有解，那么$\mathcal{X}$也有解。 我们证明，如果$\mathcal{D}$不允许循环同态，因此根据 CSP 二分定理它是 NP 完全的，那么$K_\mathcal{D}$在 ZF 上等价于布尔素理想定理（BPI）。相反，我们还证明，如果$\mathcal{D}$允许循环同态，因此它在 P 中，那么$K_\mathcal{D}$严格弱于 BPI。