Theorem 7 —
ProvedExtensionComplexity.TSP.xc_cor_lower_boundcorrelation-polytopecut-polytopeextension-complexitylower-boundp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Theorem 7: there is a constant such that for all ,
In particular, the extension complexity of is : there are and with for all .
This is the first exponential lower bound on the extension complexity of a polytope associated with an NP-hard problem (max-cut), and it is the base of the reductions to the stable set and TSP polytopes.
Formalization Note The page says "for all ". At both and are single points, whose extension complexity is , so the printed statement fails there; the hypothesis is added. The second conjunct is the "In particular" sentence, with read as .
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ExtensionComplexity_TSP_CutCor
Formal statement
namespace ExtensionComplexity.TSP
/-- **Theorem 7** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:12): there is a constant
`C > 0` such that for all `n ≥ 1`, `xc(CUT(n+1)) = xc(COR(n)) ≥ 2^{Cn}`. In particular the
extension complexity of `CUT(n)` is `2^{Ω(n)}`. The page says "for all n"; at `n = 0` both
polytopes are single points with `xc = 0 < 2^0`, so `n ≥ 1` is added. -/
theorem xc_cor_lower_bound :
(∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 1 ≤ n →
extensionComplexity (cutPolytope (n + 1)) = extensionComplexity (corPolytope n) ∧
(2 : ℝ) ^ (C * n) ≤ (extensionComplexity (corPolytope n) : ℝ)) ∧
(∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, ∀ n ≥ N,
(2 : ℝ) ^ (C * n) ≤ (extensionComplexity (cutPolytope 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:12, Theorem 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.