<div class="csl-bib-body">
<div class="csl-entry">Creignou, N., Hermann, M., Krokhin, A., & Salzer, G. (2008). Complexity of Clausal Constraints Over Chains. <i>Theory of Computing Systems</i>, <i>42</i>(2), 239–255. https://doi.org/10.1007/s00224-007-9003-z</div>
</div>
-
dc.identifier.issn
1432-4350
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/169710
-
dc.description.abstract
We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints based on clausal patterns. A pattern abstracts away from variables and contains only information about the domain elements and the type of inequalities occurring in a constraint. Every finite set of patterns gives rise to a (clausal) constraint satisfaction problem in which all constraints in instances must have an allowed pattern. We prove that every such problem is either polynomially decidable or NP-complete, and give a polynomial-time algorithm for recognizing the tractable cases. Some of these tractable cases are new and have not been previously identified in the literature.
en
dc.language.iso
en
-
dc.relation.ispartof
Theory of Computing Systems
-
dc.subject
Constraint satisfaction problems
en
dc.subject
Complexity
en
dc.subject
Finite totally ordered domains
en
dc.subject
Inequalities
en
dc.subject
Clausal patterns
en
dc.subject
dichotomy theorem
en
dc.title
Complexity of Clausal Constraints Over Chains
en
dc.type
Artikel
de
dc.type
Article
en
dc.contributor.affiliation
French National Centre for Scientific Research, France
-
dc.contributor.affiliation
École Polytechnique, France
-
dc.contributor.affiliation
Durham University, United Kingdom of Great Britain and Northern Ireland (the)
