The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913566535188480 |
|---|---|
| author | Kátay, Tamás Tóth, László Márton Vidnyánszky, Zoltán |
| author_facet | Kátay, Tamás Tóth, László Márton Vidnyánszky, Zoltán |
| contents | 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 $\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_00514 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms Kátay, Tamás Tóth, László Márton Vidnyánszky, Zoltán Logic Computational Complexity 03E25, 68Q17 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 $\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. |
| title | The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms |
| topic | Logic Computational Complexity 03E25, 68Q17 |
| url | https://arxiv.org/abs/2310.00514 |