On a decision procedure for quantified linear programs

DOI10.1007/S10472-007-9085-YzbMath1132.68034OpenAlexW2034752994MaRDI QIDQ2462634

K. Subramani and Vahan Mkrtchyan

Publication date: 3 December 2007

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-007-9085-y

zbMATH Keywords

Linear programmingAlternating Turing machinescoNP-hardnessQuantificationPolynomial-time decidability

Mathematics Subject Classification ID

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

Related Items (8)

Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic ⋮ On the complexity of quantified linear systems ⋮ Solving multistage quantified linear optimization problems with the alpha-beta nested Benders decomposition ⋮ A complexity perspective on entailment of parameterized linear constraints ⋮ Analyzing restricted fragments of the theory of linear arithmetic ⋮ On quantified linear implications ⋮ Multistage Optimization with the Help of Quantified Linear Programming ⋮ Complexity bounds for the controllability of temporal networks with conditions, disjunctions, and uncertainty

Uses Software

• RSOLVER
• HSolver

Cites Work

• Quantifier elimination for real algebra -- the quadratic case and beyond
• On Fourier's algorithm for linear arithmetic constraints
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A theory of timed automata
• Bilevel and multilevel programming: A bibliography review
• Using integer programming to verify general safety and liveness properties
• Bilevel linear programming
• Fourier-Motzkin elimination and its dual
• Applying Linear Quantifier Elimination
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Applying interval arithmetic to real, integer, and boolean constraints
• Parametric dispatching of hard real-time tasks
• Hybrid Systems: Computation and Control
• The complexity theory companion
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On a decision procedure for quantified linear programs