On the complexity of quantified integer programming

Quantified integer programming is the the problem of deciding assertions of the form "Q x_k … forall x_2 exists x_1: A x geq 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 that quantified integer programming with alternation depth k is complete for the k-th level of the polynomial hierarchy. Abstract available in PDF.

Authors

• Dmitry Chistikov
• Christoph Haase

Keywords

No keywords are indexed for this paper.