Universal Algebra and Hardness Results for Constraint Satisfaction Problems
From MaRDI portal
Publication:5428815
DOI10.1007/978-3-540-73420-8_25zbMath1171.68731MaRDI 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
08A70: Applications of universal algebra in computer science
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Path homomorphisms, graph colorings, and boolean matrices, Recent Results on the Algebraic Approach to the CSP, Dualities for Constraint Satisfaction Problems, Homomorphisms of random paths, The complexity of satisfiability problems: Refining Schaefer's theorem, On the CSP Dichotomy Conjecture, CSP dichotomy for special triads
