Some lower bounds for the complexity of the linear programming feasibility problem over the reals

RAFAEL GRIMSON; BART KUIJPERS

JOURNAL OF COMPLEXITY

ACADEMIC PRESS

Año: 2009 vol. 25 p. 25 - 37

0885-064X

We analyze the arithmetic complexity of the linear programming feasibility problem over the reals. For the case of polyhedra defined by 2n half-spaces in Rn we prove that the set I.2n;n/, of parameters describing nonempty polyhedra, has an exponential number of limiting hypersurfaces. From this geometric result we obtain, as a corollary, the existence of a constant c > 1 such that, if dense or sparse representation is used to code polynomials, the length of any quantifier-free formula expressing the set I.2n;n/ is bounded from below by .cn/. Other related complexity results are stated; in particular, a lower bound for algebraic computation trees based on the notion of limiting hypersurface is presented.