The Computational Complexity of Integer Programming with Alternations
Danny Nguyen, Igor Pak · Mathematics of Operations Research · 2019
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 [Formula: see text], 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.