Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4609029 | Journal of Complexity | 2009 | 13 Pages |
Abstract
We analyze the arithmetic complexity of the linear programming feasibility problem over the reals. For the case of polyhedra defined by 2n2n half-spaces in Rn we prove that the set I(2n,n)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>1c>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)I(2n,n) is bounded from below by Ω(cn)Ω(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.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Rafael Grimson, Bart Kuijpers,