Essential Convexity and Complexity of Semi-Algebraic Constraints

DOI10.2168/LMCS-8(4:5)2012zbMATH Open1253.68143arXiv1210.0420MaRDI QIDQ3166226FDOQ3166226

Peter Jonsson, Manuel Bodirsky, Timo von Oertzen

Publication date: 22 October 2012

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

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

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)

Cited In (14)

• Title not available (Why is that?)
• Max-Closed Semilinear Constraint Satisfaction
• Tractability conditions for numeric CSPs
• Constraint Satisfaction Problems over Numeric Domains
• On classifying continuous constraint satisfaction problems
• Title not available (Why is that?)
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Tropically convex constraint satisfaction
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Algebraic properties of multilinear constraints
• Complexity of reachability problems in neural networks
• Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic
• Recent contributions to linear semi-infinite optimization
• Recent contributions to linear semi-infinite optimization: an update

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)