Abstract | ||
---|---|---|
Let be a structure with a finite relational signature and a first-order definition in (R; *, +) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for Gamma: the problem to decide whether a given primitive positive sentence is true in Gamma. We focus on those structures Gamma that contain the relations <=, {(x, y, z) vertical bar x + y - z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a, b is an element of S, there are only fi nitely many points on the line segment between a and b that are not in S. If Gamma contains a relation S that is not essentially convex and this is witnessed by rational points a, b, then we show that the CSP for Gamma is NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if Gamma is a fi rst-order expansion of (R;+, 1, <=), then the CSP for Gamma can be solved in polynomial time if and only if all relations in Gamma are essentially convex (unless P = NP). |
Year | DOI | Venue |
---|---|---|
2012 | 10.2168/LMCS-8(4:5)2012 | LOGICAL METHODS IN COMPUTER SCIENCE |
Keywords | Field | DocType |
Constraint Satisfaction Problem,Convexity,Computational Complexity,Linear Programming | Discrete mathematics,Combinatorics,Convexity,Algebraic number,Relational structure,Real number,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 4 | 1860-5974 |
Citations | PageRank | References |
42 | 1.61 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manuel Bodirsky | 1 | 644 | 54.63 |
Peter Jonsson | 2 | 700 | 54.04 |
Timo Von Oertzen | 3 | 71 | 7.84 |