Tractability conditions for numeric CSPs

Abstract : The computational complexity of the constraint satisfaction problem (CSP) with semilinear relations over the reals has gained recent attraction. As a result, its complexity is known for all finite sets of semilinear relations containing the relation R + = {(x, y, z) ∈ R 3 | x + y = z}. We consider larger and more expressive classes of relations such as semialgebraic and o-minimal relations. We present a general result for characterising computationally hard fragments and, under certain side conditions, this result implies that polynomial-time solvable fragments are only to be found within two limited families of sets of relations. In the setting of semialgebraic relation, our result takes on a simplified form and we provide a full complexity classification for constraint languages that consist of algebraic varieties. Full classifications like the one obtained here for algebraic varieties or the one for semilinear relations appear to be rare and we discuss several barriers for obtaining further such results. These barriers have strong connections with well-known open problems concerning the complexity of various restrictions of convex programming.
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01796723
Contributor : Johan Thapper <>
Submitted on : Monday, May 21, 2018 - 9:30:29 PM
Last modification on : Friday, April 12, 2019 - 10:18:10 AM
Long-term archiving on : Monday, September 24, 2018 - 1:47:16 PM

File

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

Identifiers

Citation

Peter Jonsson, Johan Thapper. Tractability conditions for numeric CSPs. Theoretical Computer Science, Elsevier, 2018, 715, pp.21 - 34. ⟨10.1016/j.tcs.2018.01.013⟩. ⟨hal-01796723⟩

Share

Metrics

Record views

109

Files downloads

127