Strong subalgebras and the constraint satisfaction problem

MaRDI QIDQ5863609FDOQ5863609

Authors: D. N. Zhuk 

Publication date: 3 June 2022

Full work available at URL: https://arxiv.org/abs/2005.00593

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

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)

Cites Work

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

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
• Strong subalgebras and the Constraint Satisfaction Problem
• Submaximal clones over a three-element set up to minor-equivalence
• 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)