2011/04/30 by Thomas Rothvoß, Rothvoß, Thomas
Computer Science · Engineering · Mathematics · #52B11 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #acm:52B11 #cs.CC #cs.DM #graph theory and CDMA systems #math.CO #msc:52B11
paper · pdf · doi:10.48550/arxiv.1105.0036
arxiv created 2011/04/30 · openalex publication_date 2011/04/30 · arxiv updated 2011/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that there are 0/1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X ⊆ 0,1n such that conv(X) must have extension complexity at least 2n/2 * (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 NP not contained in P/poly, our result rules out the existence of any compact formulation for the TSP polytope, even if the formulation may contain arbitrary real numbers.