Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2404.01080 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Table des matières:
- 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.