Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Johan Thapper Connect in order to contact the contributor
Submitted on : Monday, May 21, 2018 - 9:30:29 PM
Last modification on : Monday, September 19, 2022 - 9:16:54 AM
Long-term archiving on: : Monday, September 24, 2018 - 1:47:16 PM


Files produced by the author(s)



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⟩



Record views


Files downloads