The Library
On the complexity of quantified integer programming
Tools
Tools
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. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2017.94
|
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 > 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 | ||||||
| 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
