Manuel Bodirsky ; Peter Jonsson ; Timo von Oertzen - Essential Convexity and Complexity of Semi-Algebraic Constraints

lmcs:1218 - Logical Methods in Computer Science, October 10, 2012, Volume 8, Issue 4 - https://doi.org/10.2168/LMCS-8(4:5)2012
Essential Convexity and Complexity of Semi-Algebraic Constraints

Authors: Manuel Bodirsky ; Peter Jonsson ; Timo von Oertzen

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


    Volume: Volume 8, Issue 4
    Published on: October 10, 2012
    Accepted on: June 25, 2015
    Submitted on: December 6, 2009
    Keywords: Computer Science - Computational Complexity,Computer Science - Discrete Mathematics,Mathematics - Logic,F.2.2, F.4.1, G.1.6
    Fundings :
      Source : OpenAIRE Research Graph
    • Constraint Satisfaction Problems: Algorithms and Complexity; Funder: European Commission; Code: 257039

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 2007.01779
    Source : ScholeXplorer IsCitedBy DOI 10.1145/3458041
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.mfcs.2020.85
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2007.01779
    • 10.1145/3458041
    • 10.1145/3458041
    • 10.4230/lipics.mfcs.2020.85
    • 10.48550/arxiv.2007.01779
    • 2007.01779
    The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
    Viola, Caterina ; Živný, Stanislav ;

    13 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 437 times.
    This article's PDF has been downloaded 205 times.