Theorem 3 (Yannakakis) — iff an extension with facets iff an EF with inequalities
ProvedExtensionComplexity.TSP.yannakakis_factorizationextension-complexityfactorization-theoremnonnegative-rankp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1yannakakis
Let be a polytope with , and , of dimension , and let be the slack matrix of with respect to and . Theorem 3 (Yannakakis 1991): for every positive integer the following are equivalent:
- ;
- has an extension of size at most , i.e. a polytope with at most facets and a linear map with ;
- has an EF of size at most , i.e. with at most inequalities.
In short, : lower bounds on extension complexity are lower bounds on the nonnegative rank of any slack matrix, and conversely.
Formalization Note is for a finite index type . is stated as " contains two distinct points", which is equivalent for a nonempty convex set. The slack matrix is taken with respect to the given (not only facets and vertices). Condition 2 lets the ambient dimension of be any natural number; condition 3 is "an EF of some size ".
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ExtensionComplexity_TSP_Polytope import Definitions.Def_ExtensionComplexity_TSP_SlackMatrix open Matrix
Formal statement
namespace ExtensionComplexity.TSP
/-- **Theorem 3** [Yannakakis 1991] (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:10): let
`P = {x | Ax ≤ b} = conv(V)` be a polytope with `dim(P) ≥ 1`, and let `S` be the slack matrix of
`P` with respect to `Ax ≤ b` and `V`. For every positive integer `r` the following are equivalent:
(i) `rank₊(S) ≤ r`; (ii) `P` has an extension with at most `r` facets; (iii) `P` has an EF with at
most `r` inequalities. `dim(P) ≥ 1` is stated as: `P` contains two distinct points. -/
theorem yannakakis_factorization {ι : Type*} [Fintype ι] {m N : ℕ}
(A : Matrix (Fin m) ι ℝ) (b : Fin m → ℝ) (V : Fin N → ι → ℝ) (P : Set (ι → ℝ))
(hPA : P = {x | A *ᵥ x ≤ b}) (hPV : P = convexHull ℝ (Set.range V))
(hdim : ∃ x ∈ P, ∃ y ∈ P, x ≠ y) (r : ℕ) (hr : 1 ≤ r) :
List.TFAE
[nonnegRank (slackMatrix A b V) ≤ r,
∃ (e : ℕ) (Q : Set (Fin e → ℝ)), IsExtension Q P ∧ HasAtMostFacets Q r,
∃ r' ≤ r, IsEFOfSize P r'] := 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:10, Theorem 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.