A lower bound for the complexity of linear optimization from a quantifier-elimination point of view

RAFAEL GRIMSON

Dagstuhl, Alemania

Congreso; Constraint Databases, Geometric Elimination and Geographic Information Systems; 2007

We analyze the arithmetic complexity of the feasibility problem in linear optimization theory as a quantifier-elimination problem. For the case of polyhedra defined by 2n halfspaces in R^n we prove that, if dense representation is used to code polynomials, any quantifier-free formula expressing the set of parameters describing nonempty polyhedra has size at least 4^n.