Universal algebra and hardness results for constraint satisfaction problems

DOI10.1016/j.tcs.2008.12.048zbMath1172.68024OpenAlexW2027524199MaRDI QIDQ1014634

Pascal Tesson, Benoit Larose

Publication date: 29 April 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.048

zbMATH Keywords

constraint satisfactionDataloguniversal algebracomplexity classes

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 (25)

On a stronger reconstruction notion for monoids and clones ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ CSP for binary conservative relational structures ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ List-homomorphism problems on graphs and arc consistency ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ The Complexity of Valued CSPs ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Rigid binary relations on a 4-element domain ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ The complexity of the list homomorphism problem for graphs ⋮ CSP duality and trees of bounded pathwidth ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ On algebras with many symmetric operations ⋮ OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT ⋮ The number of clones determined by disjunctions of unary relations ⋮ Idempotent n -permutable varieties ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• On the expressive power of Datalog: tools and a case study.
• Bounded width problems and algebras
• Storage requirements for deterministic polynomial time recognizable languages
• On the algebraic structure of combinatorial problems
• Finite posets and topological spaces in locally finite varieties
• Parity, circuits, and the polynomial-time hierarchy
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
• Undirected ST-connectivity in log-space
• Structure and importance of logspace-MOD class
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Linear Datalog and Bounded Path Duality of Relational Structures
• The complexity of satisfiability problems
• Affine Systems of Equations and Counting Infinitary Logic
• A Characterisation of First-Order Constraint Satisfaction Problems
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Universal algebra and hardness results for constraint satisfaction problems