Conference item
On the complexity of quantified integer programming
- Abstract:
- Quantified integer programming is the the problem of deciding assertions of the form Qkxk . . . ∀x2 ∃x1 : A·x ≥ c where vectors of variables xk, . . . , x1 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 597.2KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2017.94
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
- Journal:
- ICALP 2017 More from this journal
- Volume:
- 80
- Pages:
- 94:1--94:13
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Publication date:
- 2017-07-06
- Acceptance date:
- 2017-04-14
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959770415
- Keywords:
- Pubs id:
-
pubs:692253
- UUID:
-
uuid:0c9969ae-1e92-45c5-8786-7dba50b6d2ab
- Local pid:
-
pubs:692253
- Source identifiers:
-
692253
- Deposit date:
-
2017-05-03
- ARK identifier:
Terms of use
- Copyright holder:
- Chistikov and Haase
- Copyright date:
- 2017
- Notes:
-
Copyright © 2017 Dmitry Chistikov and Christoph Haase;
licensed under Creative Commons License CC-BY.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record