Universal Algebra and Hardness Results for Constraint Satisfaction Problems
From MaRDI portal
Publication:5428815
DOI10.1007/978-3-540-73420-8_25zbMath1171.68731OpenAlexW1555655798MaRDI QIDQ5428815
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
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
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