Strong subalgebras and the constraint satisfaction problem

MaRDI QIDQ5863609zbMATH OpenFDO

Authors D. N. Zhuk

Publication date 3 June 2022

Full work available at URL https://arxiv.org/abs/2005.00593, https://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-36-number-4-5-2021/mvlsc-36-4-5-p-455-504/

zbMATH Keywords

computational complexityconstraint satisfaction problemweak near-unanimitystrong subalgebrasCSP Dichotomy conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Subalgebras, congruence relations (08A30)

Recommendations

• A proof of the CSP dichotomy conjecture
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Universal algebra and hardness results for constraint satisfaction problems
• scientific article; zbMATH DE number 1670830
• Constraint satisfaction problems over finite structures

Cites work

• scientific article; zbMATH DE number 4035895 (Why is no real title available?)
• A characterization of polynomially complete algebras
• A proof of the CSP dichotomy conjecture
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Algebras in permutable varieties: Geometrical properties of affine algebras
• Characterising tractable constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Closure properties of constraints
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Deciding absorption
• Fast parallel constraint satisfaction
• Function Algebras on Finite Sets
• Key (critical) relations preserved by a weak near-unanimity function
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• On the algebraic structure of combinatorial problems
• Recent Results on the Algebraic Approach to the CSP
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Tractable constraints on ordered domains
• Weak consistency notions for all the CSPs of bounded width

Cited in

(7)

• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• On the descriptive complexity of temporal constraint satisfaction problems
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Submaximal clones over a three-element set up to minor-equivalence
• Strong subalgebras and the Constraint Satisfaction Problem
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Constraint satisfaction problem: what makes the problem easy

This page was built for publication: Strong subalgebras and the constraint satisfaction problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5863609)