2024/04/01 by Dmitriy Zhuk, Zhuk, Dmitriy · 2 voices
Computer Science · Mathematics · #Advanced Topics in Algebra #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Rings and Algebras (math.RA) #cs.CC #cs.LO #math.RA
paper · pdf · doi:10.48550/arxiv.2404.01080
openalex publication_date 2024/04/01 · arxiv published 2024/04/01 · openalex created_date 2024/04/03 · arxiv updated 2024/10/21 · openalex updated_date 2026/07/28
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.