Summary: | 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 relations \leq, {(x,y,z) | 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\inS, 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;*,+), 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).
|