Affine consistency and the complexity of semilinear constraints - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Affine consistency and the complexity of semilinear constraints

Résumé

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.
Fichier principal
Vignette du fichier
jt14mfcs-preprint.pdf (442.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01762331 , version 1 (09-04-2018)

Identifiants

  • HAL Id : hal-01762331 , version 1

Citer

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⟩
140 Consultations
67 Téléchargements

Partager

Gmail Facebook X LinkedIn More