Manuel Bodirsky
Essential Convexity and Complexity of Semi-algebraic Constraints
With Peter Jonsson and Timo von Oertzen; submitted for journal publication. A preliminary version appeared under the title "Semilinear program feasiblity" in the proceedings of ICALP 2009, pages 79-90.
Abstract
Let Gamma 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 inequality relation ≤, the relation defined by x+y=z, and the unary relation that contains the constant 1 only. 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 in S, there are only finitely 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 first-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).
Download
