Abstract
A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets Γ of semilinear relations containing the relations R + = {(x,y,z) | x + y = z}, ≤, and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(Γ) for semilinear Γ containing R + and satisfying two auxiliary conditions. Our result covers all semilinear Γ such that {R + ,{1}} ⊆ Γ. We continue by studying the more general case when Γ contains R + but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial.
Partially supported by the Swedish Research Council (VR) under grant 621-2012-3239.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Polynomial Time
- Constraint Satisfaction
- Constraint Satisfaction Problem
- Auxiliary Condition
- Unary Relation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bodirsky, M., Grohe, M.: Non-dichotomies in constraint satisfaction complexity. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 184–196. Springer, Heidelberg (2008)
Bodirsky, M., Jonsson, P., von Oertzen, T.: Essential convexity and complexity of semi-algebraic constraints. Logical Methods in Computer Science 8(4) (2012)
Bodirsky, M., Jonsson, P., von Oertzen, T.: Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction. J. Log. Comput. 22(3), 643–660 (2012)
Bodirsky, M., Kára, J.: The complexity of temporal constraint satisfaction problems. J. ACM 57(2) (2010)
Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66–120 (2006)
Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the computational complexity of constraints using finte algebras. SIAM J. Comput. 34(3), 720–742 (2005)
Feder, T., Vardi, M.Y.: Monotone monadic SNP and constraint satisfaction. In: Proceedings of the 25th ACM Symposium on Theory of Computing (STOC 1993), pp. 612–622 (1993)
Hell, P., Nešetřil, J.: Colouring, constraint satisfaction, and complexity. Computer Science Review 2(3), 143–163 (2008)
Jonsson, P., Lööw, T.: Computational complexity of linear constraints over the integers. Artif. Intell. 195, 44–62 (2013)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC 1978), pp. 216–226 (1978)
Schrijver, A.: Theory of linear and integer programming. John Wiley & Sons (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jonsson, P., Thapper, J. (2014). Affine Consistency and the Complexity of Semilinear Constraints. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_36
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)