  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
$\max\limits_{x \in P} 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 $|X|$, 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$, $|Y| = n$, such that the algorithm
$A$ requires exponential time or space for solving $Y$.
