An algebraic hardness criterion for surjective constraint satisfaction.

DOI10.1007/s00012-014-0308-xzbMath1308.08001arXiv1405.4917OpenAlexW2038274600MaRDI QIDQ485113

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

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

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems

Cites Work

• The complexity of surjective homomorphism problems-a survey
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Graph partitions with prescribed patterns
• Closed systems of functions and predicates
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• On generating all solutions of generalized satisfiability problems
• Max-Sur-CSP on Two Elements
• Constraint Satisfaction Problems of Bounded Width
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers

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