Essential convexity and complexity of semi-algebraic constraints

DOI10.2168/LMCS-8(4:5)2012MaRDI QIDQ3166226zbMATH OpenFDO

Authors Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

Publication date 22 October 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.0420

zbMATH Keywords

computational complexitylinear programmingconvexityconstraint satisfaction problemessential convexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in computer science (03B70)

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 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,binS, 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).

Recommendations

• Tractability conditions for numeric CSPs
• Affine consistency and the complexity of semilinear constraints
• Semilinear Program Feasibility
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Constraint satisfaction problems over numeric domains

Cited in

(16)

• Tropically convex constraint satisfaction
• Complexity of reachability problems in neural networks
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• MAX-closed semilinear constraint satisfaction
• Algebraic properties of multilinear constraints
• Recent contributions to linear semi-infinite optimization: an update
• Constraint satisfaction problems over numeric domains
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Semilinear Program Feasibility
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Affine consistency and the complexity of semilinear constraints
• Tractability conditions for numeric CSPs
• Recent contributions to linear semi-infinite optimization
• scientific article; zbMATH DE number 7378350 (Why is no real title available?)
• On classifying continuous constraint satisfaction problems
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains

This page was built for publication: Essential convexity and complexity of semi-algebraic constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3166226)