Benoit Larose ; Cynthia Loten ; Claude Tardif - A Characterisation of First-Order Constraint Satisfaction Problems

lmcs:1097 - Logical Methods in Computer Science, November 6, 2007, Volume 3, Issue 4 - https://doi.org/10.2168/LMCS-3(4:6)2007
A Characterisation of First-Order Constraint Satisfaction ProblemsArticle

Authors: Benoit Larose ; Cynthia Loten ; Claude Tardif

    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.


    Volume: Volume 3, Issue 4
    Published on: November 6, 2007
    Imported on: March 2, 2007
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,F.4.1
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    30 Documents citing this article

    Consultation statistics

    This page has been seen 1061 times.
    This article's PDF has been downloaded 276 times.