Change search
ReferencesLink to record
Permanent link

Direct link
Essential Convexity and Complexity of Semi-algebraic Constraints
Ecole Polytechnique, Palaiseau, France. (LIX)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Max-Planck-Institute for Human Development, Berlin, Germany and University of Virginia, Charlottesville, USA..
2012 (English)In: Logical Methods in Computer Science, ISSN 1860-5974, Vol. 8, no 4Article in journal (Refereed) Published
Abstract [en]

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,b\inS, 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).

Place, publisher, year, edition, pages
International Federation for Computational Logic , 2012. Vol. 8, no 4
National Category
Computer Science
URN: urn:nbn:se:liu:diva-86698DOI: 10.2168/LMCS-8(4:5)2012ISI: 000315381600012OAI: diva2:580423
Available from: 2012-12-21 Created: 2012-12-21 Last updated: 2014-10-28

Open Access in DiVA

fulltext(591 kB)24 downloads
File information
File name FULLTEXT01.pdfFile size 591 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textLink to article

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsThe Institute of Technology
In the same journal
Logical Methods in Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 24 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 79 hits
ReferencesLink to record
Permanent link

Direct link