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.
No takes yet. Share an insight, caveat, or question.
Dmitriy Zhuk (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: