It is well known that Linear Programming is P-complete, with a logspace reduction. In this work we ask whether Linear Programming remains P-complete, even if the polyhedron (i.e., the set of linear inequality constraints) is a fixed polyhedron, for each input size, and only the objective function is given as input.

More formally, we consider the following problem: maximize $c\cdot x$, subject to $Ax\leq b; x \in \mathbb{R}^d$, where $A,b$ are fixed in advance and only $c$ is given as an input.

We start by showing that the problem remains P-complete with a logspace reduction, thus showing that $n^{o(1)}$-space algorithms are unlikely. This result is proved by a direct classical reduction.

We then turn to study approximation algorithms and ask what is the best approximation factor that could be obtained by a small space algorithm. Since approximation factors are mostly meaningful when the objective function is non-negative, we restrict ourselves to the case where $x \geq 0$ and $c \geq 0$.
We show that (even in this possibly easier case) approximating the value of max $c\cdot x$ (within any polynomial factor) is P-complete with a polylog space reduction, thus showing that $2^{(\log n)^{o(1)}}$-space approximation algorithms are unlikely.

The last result is proved using a recent work of Kalai, Raz, and Rothblum, showing that every language in P has a no-signaling multi-prover interactive proof with poly-logarithmic communication complexity. To the best of our knowledge, our result gives the first space hardness of approximation result proved by a PCP-based argument.

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large space. Specifically, it was shown that (approximating) Linear Programming is P complete with a logspace reduction, thus showing that $n^{o(1)}$-space algorithms for (approximating) Linear Programming are unlikely.

We show that (approximating) Linear Programming is likely to have a large space complexity, even if we allow a preprocessing phase that takes the polyhedron as input and runs in unbounded time and space. Specifically, we prove that (approximating) Linear Programming with such ``preprocessing'' is P complete with a poly-logarithmic space and quasi-polynomial time reduction, thus showing that $2^{(\log n)^{o(1)}}$-space algorithms for Linear Programming with ``preprocessing'' are unlikely.

We obtain our result using a recent work of Kalai, Raz and Rothblum, showing that every language in P has a no-signalling multi-prover interactive proof with poly-logarithmic communication complexity. To the best of our knowledge, this is the first space hardness of approximation result proved by a PCP based argument.