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.