{
  "id": "2310.00514",
  "version": "v1",
  "published": "2023-09-30T22:31:54.000Z",
  "updated": "2023-09-30T22:31:54.000Z",
  "title": "The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms",
  "authors": [
    "Tamás Kátay",
    "László Márton Tóth",
    "Zoltán Vidnyánszky"
  ],
  "categories": [
    "math.LO",
    "cs.CC"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-30T22:31:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03E25",
      "68Q17"
    ],
    "keywords": [
      "cyclic polymorphism",
      "boolean prime ideal theorem",
      "study constraint satisfaction problems",
      "csp dichotomy theorem",
      "infinite context"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}