Chistikov, D;
Haase, C;
(2017)
On the complexity of quantified integer programming.
In:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017).
(pp. 94:1-94:13).
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany.
Preview |
Text
LIPIcs-ICALP-2017-94.pdf - Published Version Download (611kB) | Preview |
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.
| Type: | Proceedings paper |
|---|---|
| Title: | On the complexity of quantified integer programming |
| Event: | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
| ISBN-13: | 9783959770415 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.ICALP.2017.94 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.ICALP.2017.94 |
| Language: | English |
| Additional information: | © Dmitry Chistikov and Christoph Haase; licensed under Creative Commons License CC-BY |
| Keywords: | Integer programming, semi-linear sets, Presburger arithmetic, quantifier elimination |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10088923 |
Archive Staff Only
 |
View Item |
