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-5481 and Kannan [13,14] [Kannan R (1990) Test sets for integer programs, for all there exists 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.1 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 of 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.