|
|
VOLUME 3, ISSUE 4, PAPER 6
|
A Characterisation of First-Order Constraint Satisfaction Problems
|
©Benoit Larose, Concordia University
©Cynthia Loten, University College of the Fraser Valley
©Claude Tardif, Royal Military College of Canada
|
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.
|
Publication date: November 6, 2007
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-3(4:6)2007
Hit Counts: 5159 |
 Creative Commons | |
