Document Open Access Logo

On the Complexity of Quantified Integer Programming

Authors Dmitry Chistikov, Christoph Haase

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.94.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Author Details

Dmitry Chistikov
Christoph Haase

Cite AsGet BibTex

Dmitry Chistikov and Christoph Haase. On the Complexity of Quantified Integer Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 94:1-94:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.94

Abstract

Quantified integer programming is the problem of deciding assertions of the form Q_k x_k ... forall x_2 exists x_1 : A * x >= c where vectors of variables x_k,..,x_1 form the vector x, all variables are interpreted over N (alternatively, over Z), and A and c are a matrix and vector over Z of appropriate sizes. We show in this paper that quantified integer programming with alternation depth k is complete for the kth level of the polynomial hierarchy.
Keywords
  • integer programming
  • semi-linear sets
  • Presburger arithmetic
  • quantifier elimination

Metrics

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

References

  1. Leonard Berman. The complexitiy of logical theories. Theor. Comput. Sci., 11:71-77, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90037-7.
  2. Dmitry Chistikov and Christoph Haase. The taming of the semi-linear set. In Automata, Languages, and Programming, ICALP, volume 55 of LIPIcs, pages 128:1-128:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.128.
  3. Dmitry Chistikov, Christoph Haase, and Simon Halfon. Context-free commutative grammars with integer counters and resets. Theor. Comput. Sci., pages -, 2017. To appear. URL: http://dx.doi.org/10.1016/j.tcs.2016.06.017.
  4. Seymour Ginsburg. The mathematical theory of context-free languages. McGraw-Hill, 1966. Google Scholar
  5. Erich Grädel. Dominoes and the complexity of subclasses of logical theories. Ann. Pure Appl. Logic, 43(1):1-30, 1989. URL: http://dx.doi.org/10.1016/0168-0072(89)90023-7.
  6. Christoph Haase. Subclasses of Presburger arithmetic and the weak EXP hierarchy. In Computer Science Logic and Logic in Computer Science, CSL-LICS, pages 47:1-47:10. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603092.
  7. Ravi Kannan. Test sets for integer programs, ∀ ∃ sentences. In Polyhedral Combinatorics, Proceedings of a DIMACS Workshop, Morristown, New Jersey, USA, June 12-16, 1989, pages 39-48, 1990. Google Scholar
  8. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  9. Felix Klaedtke. Bounds on the automata size for Presburger arithmetic. ACM Trans. Comput. Log., 9(2):11:1-11:34, 2008. URL: http://dx.doi.org/10.1145/1342991.1342995.
  10. Jiri Matoušek. Lectures on discrete geometry. Graduate texts in mathematics. Springer, 2002. URL: http://dx.doi.org/10.1007/978-1-4613-0039-7.
  11. Danny Nguyen and Igor Pak. Complexity of short Presburger arithmetic. In Symposium on the Theory of Computing, STOC, 2017. To appear. URL: https://arxiv.org/abs/1704.00249.
  12. Loïc Pottier. Minimal solutions of linear Diophantine systems: Bounds and algorithms. In Rewriting Techniques and Applications, RTA, volume 488 of Lect. Notes Comp. Sci., pages 162-173. Springer, 1991. URL: http://dx.doi.org/10.1007/3-540-53904-2_94.
  13. Larry J. Stockmeyer. The polynomial-time hierarchy. Theor. Comput. Sci., 3(1):1-22, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90061-X.
  14. K. Subramani. Tractable fragments of Presburger arithmetic. Theory Comput. Syst., 38(5):647-668, 2005. URL: http://dx.doi.org/10.1007/s00224-004-1220-0.
  15. Stephen D. Travers. The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci., 369(1-3):211-229, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.08.017.
  16. Joachim von zur Gathen and Malte Sieveking. A bound on solutions of linear integer equalities and inequalities. P. Am. Math. Soc., 72(1):155-158, 1978. URL: http://dx.doi.org/10.1090/S0002-9939-1978-0500555-0.
  17. Volker Weispfenning. The complexity of almost linear Diophantine problems. J. Symb. Comp., 10(5):395-403, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80051-X.
  18. Volker Weispfenning. Complexity and uniformity of elimination in Presburger arithmetic. In Symbolic and Algebraic Computation, ISSAC, pages 48-53. ACM, 1997. URL: http://dx.doi.org/10.1145/258726.258746.
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact