Affine consistency and the complexity of semilinear constraints

Abstract : A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets Γ of semilinear relations containing the relations R+ = {(x, y, z) | x+y = z}, ≤, and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(Γ) for semilinear Γ containing R+ and satisfying two auxiliary conditions. Our result covers all semilinear Γ such that {R+, {1}} ⊆ Γ. We continue by studying the more general case when Γ contains R+ but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01762331
Contributor : Johan Thapper <>
Submitted on : Monday, April 9, 2018 - 10:07:48 PM
Last modification on : Thursday, July 5, 2018 - 2:46:13 PM

File

jt14mfcs-preprint.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01762331, version 1

Citation

Peter Jonsson, Johan Thapper. Affine consistency and the complexity of semilinear constraints. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014), 2014, Budapest, Hungary. ⟨hal-01762331⟩

Share

Metrics

Record views

240

Files downloads

69