A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914979504979968 |
|---|---|
| author | Zhuk, Dmitriy |
| author_facet | Zhuk, Dmitriy |
| contents | We develop a new theory of strong subalgebras and linear congruences that are defined globally. Using this theory we provide a new proof of the correctness of Zhuk's algorithm for all tractable CSPs on a finite domain, and therefore a new simplified proof of the CSP Dichotomy Conjecture. Additionally, using the new theory we prove that composing a weak near-unanimity operation of an odd arity $n$ we can derive an $n$-ary operation that is symmetric on all two-element sets. Thus, CSP over a constraint language $Γ$ on a finite domain is tractable if and only if there exist infinitely many polymorphisms of $Γ$ that are symmetric on all two-element sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_01080 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations Zhuk, Dmitriy Computational Complexity Logic in Computer Science Rings and Algebras We develop a new theory of strong subalgebras and linear congruences that are defined globally. Using this theory we provide a new proof of the correctness of Zhuk's algorithm for all tractable CSPs on a finite domain, and therefore a new simplified proof of the CSP Dichotomy Conjecture. Additionally, using the new theory we prove that composing a weak near-unanimity operation of an odd arity $n$ we can derive an $n$-ary operation that is symmetric on all two-element sets. Thus, CSP over a constraint language $Γ$ on a finite domain is tractable if and only if there exist infinitely many polymorphisms of $Γ$ that are symmetric on all two-element sets. |
| title | A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations |
| topic | Computational Complexity Logic in Computer Science Rings and Algebras |
| url | https://arxiv.org/abs/2404.01080 |