{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:41Z","timestamp":1753889801857,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,10,10]],"date-time":"2012-10-10T00:00:00Z","timestamp":1349827200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["257039"],"award-info":[{"award-number":["257039"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Let \\Gamma be a structure with a finite relational signature and a\nfirst-order definition in (R;*,+) with parameters from R, that is, a relational\nstructure over the real numbers where all relations are semi-algebraic sets. In\nthis article, we study the computational complexity of constraint satisfaction\nproblem (CSP) for \\Gamma: the problem to decide whether a given primitive\npositive sentence is true in \\Gamma. We focus on those structures \\Gamma that\ncontain the relations \\leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied\nin this article are at least as expressive as the feasibility problem for\nlinear programs. The central concept in our investigation is essential\nconvexity: a relation S is essentially convex if for all a,b\\inS, there are\nonly finitely many points on the line segment between a and b that are not in\nS. If \\Gamma contains a relation S that is not essentially convex and this is\nwitnessed by rational points a,b, then we show that the CSP for \\Gamma is\nNP-hard. Furthermore, we characterize essentially convex relations in logical\nterms. This different view may open up new ways for identifying tractable\nclasses of semi-algebraic CSPs. For instance, we show that if \\Gamma is a\nfirst-order expansion of (R;*,+), then the CSP for \\Gamma can be solved in\npolynomial time if and only if all relations in \\Gamma are essentially convex\n(unless P=NP).<\/jats:p>","DOI":"10.2168\/lmcs-8(4:5)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:21:33Z","timestamp":1385731293000},"source":"Crossref","is-referenced-by-count":13,"title":["Essential Convexity and Complexity of Semi-Algebraic Constraints"],"prefix":"10.46298","volume":"Volume 8, Issue 4","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[]},{"given":"Timo","family":"von Oertzen","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,10,10]]},"reference":[{"key":"440:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1218\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1218\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:06:03Z","timestamp":1681243563000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,10]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(4:5)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1210.0420","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1210.0420","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,10,10]]},"article-number":"1218"}}