UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On the complexity of quantified integer programming

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. Green open access

[thumbnail of LIPIcs-ICALP-2017-94.pdf]
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
Downloads since deposit
10Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item