Some lower bounds for the complexity of the linear programming feasibility problem over the reals (Q998976): Difference between revisions

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.