Universal Algebra and Hardness Results for Constraint Satisfaction Problems

DOI10.1007/978-3-540-73420-8_25zbMath1171.68731OpenAlexW1555655798MaRDI QIDQ5428815

Pascal Tesson, Benoit Larose

Publication date: 28 November 2007

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73420-8_25

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

On the CSP Dichotomy Conjecture ⋮ Homomorphisms of random paths ⋮ Path homomorphisms, graph colorings, and boolean matrices ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ CSP dichotomy for special triads ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems

This page was built for publication: Universal Algebra and Hardness Results for Constraint Satisfaction Problems