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

clonesconstraint satisfaction problemsurjective constraint satisfaction

Mathematics Subject Classification ID

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

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.

Review text

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 an 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\). Equivalently, given a structure \(A\) over the signature of \(B\), one can decide whether or not there is a surjective homomorphism from \(A\) to \(B\). Main result: Suppose \(B\) is a finite structure which is not a singleton. If each polymorphism of \(B\) is essentially unary then the surjective CSP on \(B\) 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
• scientific article; zbMATH DE number 4114007
• 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)

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

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)