An algebraic hardness criterion for surjective constraint satisfaction.

DOI10.1007/S00012-014-0308-XMaRDI QIDQ485113zbMATH OpenOpenAlexFDO

Authors Hubie Chen

Publication date 9 January 2015

Published in Algebra Universalis (Search for Journal in Brave)

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

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)

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.

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; zbMATH DE number 4162262
• 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

Cites work

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

Cited in

(8)

• Minimum violation vertex maps and their applications to cut problems
• The data complexity of ontology-mediated queries with closed predicates
• Algebraic global gadgetry for surjective constraint satisfaction
• Surjective \texttt{H}-colouring over reflexive digraphs
• The Complexity of Boolean Surjective General-Valued CSPs
• CSP for binary conservative relational structures
• Universal algebra and hardness results for constraint satisfaction 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)