Creignou, N. and Hermann, M. and Krokhin, A. and Salzer, G. (2008) 'Complexity of clausal constraints over chains.', Theory of computing systems., 42 (2). pp. 239-255.
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.
| Item Type: | Article |
|---|---|
| Keywords: | Constraint satisfaction problems, Complexity, Finite totally ordered domains, Inequalities, Clausal patterns, Dichotomy theorem. |
| Full text: | Full text not available from this repository. |
| Publisher Web site: | http://dx.doi.org/10.1007/s00224-007-9003-z |
| Date accepted: | No date available |
| Date deposited: | No date available |
| Date of first online publication: | February 2008 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
