2026-07-21T20:32:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1283 2024-03-06T11:07:33Z ddc:004 open_access

A lower bound for the complexity of linear optimization from a quantifier-elimination point of view Grimson, Rafael Quantifier elimination dense representation instrinsic lower bound We discuss the impact of data structures in quantifier elimination. 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 $mathbb{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 $Omega(4^{n})$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rafael Grimson 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7212, Constraint Databases, Geometric Elimination and Geographic Information Systems (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07212.3 urn:nbn:de:0030-drops-12837 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.3 eng https://creativecommons.org/licenses/by/4.0/legalcode