A Characterisation of First-Order Constraint Satisfaction Problems

DOI10.2168/LMCS-3(4:6)2007zbMath1131.68098OpenAlexW2165528704MaRDI QIDQ5453499

Cynthia Loten, Benoit Larose, Claude Tardif

Publication date: 1 April 2008

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-3(4:6)2007

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Decidability of theories and sets of sentences (03B25) 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)

Related Items

Tractability in constraint satisfaction problems: a survey ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ Unnamed Item ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Constraint satisfaction, irredundant axiomatisability and continuous colouring ⋮ Dualities and dual pairs in Heyting algebras ⋮ Relativised homomorphism preservation at the finite level ⋮ List-homomorphism problems on graphs and arc consistency ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ On digraph coloring problems and treewidth duality ⋮ Majority constraints have bounded pathwidth duality ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ Majority functions on structures with finite duality ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Regular families of forests, antichains and duality pairs of relational structures ⋮ The complexity of the list homomorphism problem for graphs ⋮ Absolute retracts and varieties generated by chordal graphs ⋮ Graph partitions with prescribed patterns ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Universal algebra and hardness results for constraint satisfaction problems ⋮ Affine systems of equations and counting infinitary logic ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Unnamed Item ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems