Essential Convexity and Complexity of Semi-Algebraic Constraints

DOI10.2168/LMCS-8(4:5)2012zbMath1253.68143arXiv1210.0420MaRDI QIDQ3166226

Peter Jonsson, Manuel Bodirsky, 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

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

Related Items (11)

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 ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Recent contributions to linear semi-infinite optimization ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Recent contributions to linear semi-infinite optimization: an update ⋮ Tractability conditions for numeric CSPs ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ Unnamed Item

This page was built for publication: Essential Convexity and Complexity of Semi-Algebraic Constraints