A Characterisation of First-Order Constraint Satisfaction Problems

Abstract

We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores. A slight modification of this algorithm provides, for first-order definable CSP's, a simple poly-time algorithm to produce a solution when one exists. As an application of our algebraic characterisation of first order CSP's, we describe a large family of L-complete CSP's.

References in corpus (1)

• Linear Datalog and Bounded Path Duality of Relational Structures

Cited by in corpus (16)

• Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
• A finer reduction of constraint problems to digraphs
• The Data Complexity of Description Logic Ontologies
• Homomorphisms and Structural Properties of Relational Systems
• Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
• Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three
• Dualities and dual pairs in Heyting algebras
• Topology and adjunction in promise constraint satisfaction
• Logic Column 17: A Rendezvous of Logic, Complexity, and Algebra
• The complexity of the list homomorphism problem for graphs
• Symmetric Linear Arc Monadic Datalog and Gadget Reductions
• A dichotomy theorem for nonuniform CSPs simplified
• Low-level dichotomy for Quantified Constraint Satisfaction Problems
• Adjoint functors and tree duality