The Computational Complexity of Integer Programming with Alternations

• 成果类型: Article
• 署名作者: Danny Nguyen; Pak, Igor
• 署名单位: University of Michigan System; University of Michigan; University of California System; University of California Los Angeles
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0988
• 发表日期: 2020
• 页码: 191-204
• 关键词: rational generating-functions

摘要

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.