Complexity of LP in Terms of the Face Lattice

Let $X$ be a finite set in $Z^d$. We consider the problem of optimizing linear function $f(x)=c^{T}x$ on $X$, where $c\in Z^d$ is an input vector. We call it a problem $X$. A problem $X$ is related with linear program $\underset{x\in P}{\max }f(x)$, where polytope $P$ is a convex hull of $X$. The key parameters for evaluating the complexity of a problem $X$ are the dimension $d$, the cardinality $\mathrm{\mid }X\mathrm{\mid }$, and the encoding size $S(X) = \log_2 \left(\max\limits_{x\in X} |x|_{\infty}\right)$. We show that if the (time and space) complexity of some algorithm $A$ for solving a problem $X$ is defined only in terms of combinatorial structure of $P$ and the size $S(X)$, then for every $d$ and $n$ there exists polynomially (in $d$, $\log n$, and $S$) solvable problem $Y$ with $\dim Y=d$, $\mathrm{\mid }Y\mathrm{\mid }=n$, such that the algorithm $A$ requires exponential time or space for solving $Y$.