We prove that there are 0/1 polytopes \({P \subseteq \mathbb{R}^{n}}\) that do not admit a compact LP formulation. More precisely we show that for every n there is a set \({X \subseteq \{ 0,1\}^n}\) such that conv(X) must have extension complexity at least \({2^{n/2\cdot(1-o(1))}}\) . In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on \({\mathbf{NP}\not\subseteq \mathbf{P_{/poly}}}\) , our result rules out the existence of a compact formulation for any \({\mathbf{NP}}\) -hard optimization problem even if the formulation may contain arbitrary real numbers.
['Thomas Rothvoß']
Some 0/1 polytopes need exponential size extended formulations