The Library
On the complexity of quantified integer programming
Tools
Chistikov, Dmitry and Haase, Christoph (2017) On the complexity of quantified integer programming. In: The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 July 2017. Published in: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 80 94:1-94:13. ISBN 9783959770415. doi:10.4230/LIPIcs.ICALP.2017.94 ISSN 1868-8969.
|
PDF
WRAP-complexity-quantified-integer-Chistikov-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (926Kb) | Preview |
Official URL: 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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Integer programming, Computer science -- Mathematics | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) | ||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
ISBN: | 9783959770415 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 7 July 2017 | ||||||
Dates: |
|
||||||
Volume: | 80 | ||||||
Page Range: | 94:1-94:13 | ||||||
DOI: | 10.4230/LIPIcs.ICALP.2017.94 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 3 July 2017 | ||||||
Date of first compliant Open Access: | 4 July 2017 | ||||||
Funder: | European Research Council (ERC) | ||||||
Grant number: | VS-ISS (648701) | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | The 44th International Colloquium on Automata, Languages, and Programming (ICALP) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Warsaw, Poland | ||||||
Date(s) of Event: | 10-14 July 2017 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year