Some lower bounds for the complexity of the linear programming feasibility problem over the reals (Q998976)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Some lower bounds for the complexity of the linear programming feasibility problem over the reals |
scientific article |
Statements
Some lower bounds for the complexity of the linear programming feasibility problem over the reals (English)
0 references
30 January 2009
0 references
It is a major open question in complexity theory whether, using Boolean arithmetic circuits to codify first-order formulas, a polynomial time algorithm can be designed for the elimination of a single quantifier block. In order to find a procedure to the above problem, in this paper, the authors analyze the arithmetic complexity of linear programming. They present the subject in a wider framework. The paper is very informative and stimulating.
0 references
linear programming
0 references
algebraic complexity
0 references
limiting hypersurface
0 references
polyhedra and polytopes
0 references
complexity lower bounds
0 references
