Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
7 July 2017Published
14 April 2017Accepted
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:
  • Organisation
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us