Theorem 12 — the extension complexity of the TSP polytope is
ProvedExtensionComplexity.TSP.xc_tsp_lower_boundextension-complexitylower-boundp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1tsp-polytope
Let be the convex hull of the characteristic vectors of the tours (Hamiltonian cycles) of the complete graph , and the extension complexity, the minimum number of inequalities in a linear system , whose projection onto the -variables is the polytope. Theorem 12: the extension complexity of is ; that is, there are and such that
This answers Yannakakis's question of 1988/1991: no linear program of subexponential size, symmetric or not, projects onto the TSP polytope.
Formalization Note is read as , with a real power. The extension complexity is a natural number (the least size of an EF), so the bound cannot hold vacuously through an infinite value.
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ExtensionComplexity_TSP_TSPPolytope
Formal statement
namespace ExtensionComplexity.TSP
/-- **Theorem 12** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:16): the extension complexity
of the TSP polytope `TSP(n)` is `2^{Ω(√n)}`: there are `C > 0` and `N` with
`xc(TSP(n)) ≥ 2^{C√n}` for every `n ≥ N`. -/
theorem xc_tsp_lower_bound :
∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, ∀ n ≥ N,
(2 : ℝ) ^ (C * Real.sqrt n) ≤ (extensionComplexity (tspPolytope n) : ℝ) := by sorry
end ExtensionComplexity.TSP
Source
Fiorini, Massar, Pokutta, Tiwary, de Wolf, Exponential lower bounds for polytopes in combinatorial optimization, J. ACM 62(2) (2015), Art. 17, p. 17:16, Theorem 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.