The computational complexity of integer programming with alternations

DOI10.4230/LIPICS.CCC.2017.6MaRDI QIDQ5111136zbMATH OpenFDO

Authors Danny Nguyen, Igor Pak

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1702.08662

zbMATH Keywords

alternationsinteger programmingprojection of integer points

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Abstract: We prove that integer programming with three quantifier alternations is $NP$-complete, even for a fixed number of variables. This complements earlier results by Lenstra and Kannan, which together say that integer programming with at most two quantifier alternations 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,Qsubsetmathbb{R}^4$ , counting the projection of integer points in $$ is $$-complete. This contrasts the 2003 result by Barvinok and Woods, which allows counting in polynomial time the projection of integer points in $P$ and $Q$ separately.

Recommendations

• The computational complexity of integer programming with alternations
• On the complexity of quantified integer programming
• Integer programming in an algebraic computation model
• scientific article; zbMATH DE number 3959128
• Lower time bounds for integer programming with two variables

Cited in

(6)

• Complexity of linear relaxations in integer programming
• On the number of integer points in translated and expanded polyhedra
• Complexity of short generating functions
• Short Presburger Arithmetic Is Hard
• The computational complexity of integer programming with alternations
• On the complexity of quantified integer programming

This page was built for publication: The computational complexity of integer programming with alternations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111136)