Essential Convexity and Complexity of Semi-Algebraic Constraints

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 Γ: the problem to decide whether a given primitive positive sentence is true in Γ. We focus on those structures Γ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 Γ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 Γ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 Γis a first-order expansion of (R;*,+), then the CSP for Γcan be solved in polynomial time if and only if all relations in Γare essentially convex (unless P=NP).

25 pages, 3 Figures. An extended abstract of a preliminary version of this paper appeared in the proceedings of ICALP 2009 under the title `Semilinear Program Feasibility'

Cited by in corpus (13)

• A Uniform Substitution Calculus for Differential Dynamic Logic
• A Machine-Assisted Proof of Gödel's Incompleteness Theorems for the Theory of Hereditarily Finite Sets
• From Lock Freedom to Progress Using Session Types
• Complete algorithms for algebraic strongest postconditions and weakest preconditions in polynomial ODEs
• $\alpha$Check: A mechanized metatheory model-checker
• Towards a Ryll-Nardzewski-type Theorem for weakly oligomorphic structures
• Realizability algebras III: some examples
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• On Classifying Continuous Constraint Satisfaction Problems
• Smooth coalgebra: testing vector analysis
• A polynomial-time algorithm for median-closed semilinear constraints
• On the Computing Power of $+$, $-$, and $\times$
• Constraint Satisfaction Problems around Skolem Arithmetic