Document Open Access Logo

The Complexity of Disjunctive Linear Diophantine Constraints

Authors Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2018.33.pdf
  • Filesize: 487 kB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Constraint Satisfaction
  • Presburger Arithmetic
  • Computational Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the Constraint Satisfaction Problem CSP( A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.

Cite As Get BibTex

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet. The Complexity of Disjunctive Linear Diophantine Constraints. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.33

Author Details

Manuel Bodirsky
  • Institut für Algebra, TU Dresden, Germany
Barnaby Martin
  • Department of Computer Science, Durham University, U.K.
Marcello Mamino
  • Dipartimento di Matematica, largo Pontecorvo 5, 56127 Pisa, Italy
Antoine Mottet
  • Institut für Algebra, TU Dresden, Germany

Funding

  • Bodirsky, Manuel: Manuel Bodirsky has received funding from the ERC under the European Community’s Seventh Framework Programme (Grant Agreement no. 681988, CSP-Infinity), and the DFG-funded project `Homogene Strukturen, Bedingungserfüllungsprobleme, und topologische Klone' (Project number 622397)
  • Mamino, Marcello: Marcello Mamino has received funding from the ERC under the European Community’s Seventh Framework Programme (Grant Agreement no. 681988, CSP-Infinity).
  • Mottet, Antoine: Supported by the DFG Gratuiertenkolleg 1763 (QuantLA).

References

  1. Libor Barto, Michael Kompatscher, Miroslav Olsák, Trung Van Pham, and Michael Pinsker. The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12, 2017. URL: http://dx.doi.org/10.1109/LICS.2017.8005128.
  2. Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 2017. To appear. Preprint arXiv:1510.04521. Google Scholar
  3. Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 615-622, 2016. URL: http://dx.doi.org/10.1145/2933575.2934544.
  4. M. Bodirsky, B. Martin, and A. Mottet. Discrete temporal constraint satisfaction problems. Journal of the ACM, 65(2), 2018. preprint available at https://arxiv.org/abs/1503.08572. URL: http://dx.doi.org/10.1145/3154832.
  5. Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Antoine Mottet, and Michael Pinsker. Distance constraint satisfaction problems. Information and Computation, 247:87-105, 2016. Google Scholar
  6. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen. Essential convexity and complexity of semi-algebraic constraints. Logical Methods in Computer Science, 8(4), 2012. An extended abstract about a subset of the results has been published under the title Semilinear Program Feasibility at ICALP'10. Google Scholar
  7. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen. Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction. J. Log. Comput., 22(3):643-660, 2012. URL: http://dx.doi.org/10.1093/logcom/exr011.
  8. Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2), 2010. URL: http://dx.doi.org/10.1145/1667053.1667058.
  9. Manuel Bodirsky and Marcello Mamino. Constraint Satisfaction Problems over Numeric Domains. In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 79-111. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/DFU.Vol7.15301.79.
  10. Manuel Bodirsky, Barnaby Martin, and Antoine Mottet. Constraint satisfaction problems over the integers with successor. In Proceedings of ICALP'15, 2015. Google Scholar
  11. Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. Journal of the ACM, 62(3):Article no. 19, 1-52, 2015. A conference version appeared in the Proceedings of STOC 2011, pages 655-664. Google Scholar
  12. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Proceedings of FOCS'17, 2017. arXiv:1703.03021. Google Scholar
  13. T.-W. J. Chou and G. E. Collins. Algorithms for the solution of systems of linear diophantine equations. SIAM J. Computing, 11:687-708, 1982. Google Scholar
  14. T. Feder and M. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28:57-104, 1998. Google Scholar
  15. Peter Jonsson and Tomas Lööw. Computational complexity of linear constraints over the integers. Artificial Intelligence, 195:44-62, 2013. An extended abstract appeared at IJCAI 2011. Google Scholar
  16. Peter Jonsson and Johan Thapper. Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. J. Comput. Syst. Sci., 82(5):912-928, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2016.03.002.
  17. Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput., 8(4):499-507, 1979. Google Scholar
  18. David Marker. Model Theory: An Introduction. Springer, 2002. Google Scholar
  19. Daniele Micciancio and Bogdan Warinschi. A Linear Space Algorithm for Computing the Hermite Normal Form, pages 231-236. Association for Computing Machinery (ACM), United States, 2001. Google Scholar
  20. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  21. M. Presburger. über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Comptes Rendus du I congres de Mathématiciens des Pays Slaves, pages 92-101, 1929. Google Scholar
  22. T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of STOC'78, pages 216-226, 1978. Google Scholar
  23. Alexander Schrijver. Theory of Linear and Integer Programming. Wiley - Interscience Series in Discrete Mathematics and Optimization, 1998. Google Scholar
  24. Arne Storjohann. Computing hermite and smith normal forms of triangular integer matrices. Linear Algebra and its Applications, 282:25-45, 1998. Google Scholar
  25. Dmitriy Zhuk. The Proof of CSP Dichotomy Conjecture. In Proceedings of FOCS'17, 2017. arXiv:1704.01914. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact