On the complexity of quantified integer programming

DOI10.4230/LIPICS.ICALP.2017.94MaRDI QIDQ5111426zbMATH OpenOpenAlexFDO

Authors Christoph Haase, Dmitry Chistikov

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2017.94

zbMATH Keywords

integer programmingPresburger arithmeticquantifier eliminationsemi-linear sets

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Recommendations

• The computational complexity of integer programming with alternations
• The computational complexity of integer programming with alternations
• Automated Reasoning
• Tractable fragments of Presburger arithmetic
• On a decision procedure for quantified linear programs

Cited in

(16)

• On the complexity of quadratic programming in real number models of computation
• On the complexity of the quantified bit-vector arithmetic with binary encoding
• Polynomial time certifying algorithms for the planar quantified integer programming problem
• On the complexity of quantified linear systems
• On commensurability of right-angled Artin groups II: RAAGs defined by paths
• The computational complexity of integer programming with alternations
• The computational complexity of integer programming with alternations
• Automated Reasoning
• On the complexity of robust multi-stage problems with discrete recourse
• On polynomial-time decidability of k-negations fragments of first-order theories
• Universal quantification makes automatic structures hard to decide
• On the power of ordering in linear arithmetic theories
• Formal languages and arithmetic theories: recent results and open problems
• Universal quantification makes automatic structures hard to decide
• An introduction to the theory of linear integer arithmetic (invited paper)
• Integer programming models for the q-mode problem

This page was built for publication: On the complexity of quantified integer programming

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