2026-07-22T00:15:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7502 2024-03-06T10:40:28Z ddc:004 open_access

On the Complexity of Quantified Integer Programming Chistikov, Dmitry Haase, Christoph integer programming semi-linear sets Presburger arithmetic quantifier elimination 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Chistikov and Christoph Haase 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.94 urn:nbn:de:0030-drops-75024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.94 eng https://creativecommons.org/licenses/by/3.0/legalcode