The Computational Complexity of Integer Programming with Alternations

We prove that integer programming with three alternating quantifiers is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra [16] [Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.] and Kannan [13,14] [Kannan R (1990) Test sets for integer programs, ∀ ∃ sentences. Polyhedral Combinatorics (American Mathematical Society, Providence, RI), 39–47. Kannan R (1992) Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2):161–177.], which together say that integer programming with at most two alternating quantifiers can be done in polynomial time for a fixed number of variables. As a byproduct of the proof, we show that for two polytopes $P,Q\subset {\mathbb{R}}^3$, counting the projections of integer points in Q\P is #P-complete. This contrasts the 2003 result by Barvinok and Woods [5] [Barvinok A, Woods K (2003) Short rational generating functions for lattice point problems. J. Amer. Math. Soc. 16(4):957–979.], which allows counting in polynomial time the projections of integer points in P and Q separately.