The Computational Complexity of Integer Programming with Alternations

Danny Nguyen () and Igor Pak ()
Additional contact information
Danny Nguyen: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48105;
Igor Pak: Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095

Mathematics of Operations Research, 2020, vol. 45, issue 1, 191–204

Abstract: 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 ⊂ 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.

Keywords: integer programming; alternations; projection of integer points (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0988 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:191-204

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().