An algebraic hardness criterion for surjective constraint satisfaction.

DOI10.1007/S00012-014-0308-XzbMATH Open1308.08001arXiv1405.4917OpenAlexW2038274600MaRDI QIDQ485113FDOQ485113

Authors: Hubie Chen 

Publication date: 9 January 2015

Published in: Algebra Universalis (Search for Journal in Brave)

Abstract: The constraint satisfaction problem (CSP) on a relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is a assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic condition on the polymorphism clone of B and prove that it is sufficient for the hardness of the surjective CSP on a finite structure B, in the sense that this problem admits a reduction from a certain fixed-structure CSP. To our knowledge, this is the first result that allows one to use algebraic information from a relational structure B to infer information on the complexity hardness of surjective constraint satisfaction on B. A corollary of our result is that, on any finite non-trivial structure having only essentially unary polymorphisms, surjective constraint satisfaction is NP-complete.

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

Recommendations

• The complexity of constraint satisfaction: an algebraic approach
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Universal algebra and hardness results for constraint satisfaction problems
• scientific article
• scientific article; zbMATH DE number 1234562
• scientific article; zbMATH DE number 1670830
• SOFSEM 2004: Theory and Practice of Computer Science
• Survey propagation: An algorithm for satisfiability
• Publication:4729350
• The Complexity of Boolean Surjective General-Valued CSPs

zbMATH Keywords

constraint satisfaction problemclonessurjective constraint satisfaction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Equational classes, universal algebra in model theory (03C05) Applications of universal algebra in computer science (08A70)

Cites Work

• Complexity classifications of Boolean constraint satisfaction problems
• The complexity of surjective homomorphism problems-a survey
• Classifying the Complexity of Constraints Using Finite Algebras
• On generating all solutions of generalized satisfiability problems
• Tractability and learnability arising from algebras with few subpowers
• Closed systems of functions and predicates
• Graph partitions with prescribed patterns
• Constraint Satisfaction Problems of Bounded Width
• Max-Sur-CSP on two elements
• Computing vertex-surjective homomorphisms to partially reflexive trees

Cited In (8)

• Surjective \texttt{H}-colouring over reflexive digraphs
• Algebraic global gadgetry for surjective constraint satisfaction
• The data complexity of ontology-mediated queries with closed predicates
• The Complexity of Boolean Surjective General-Valued CSPs
• CSP for binary conservative relational structures
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Minimum violation vertex maps and their applications to cut problems
• Universal algebra and hardness results for constraint satisfaction problems

This page was built for publication: An algebraic hardness criterion for surjective constraint satisfaction.

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