Observation 21 —
ProvedTwoOptAllExp.TSP.Supplement.observation_21combinatoricslocal-searchp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every , the common length of the two canonical flip strings of Section 5 is
This gives the exponential run length in Corollary 26 and Theorem 3.
Differences from the source:
- encoding: T_n is introduced as |Ω_n| = |Ω̄_n| immediately before Observation 21 → (OmegaBar n).length = T n, where T n is defined as (Omega n).length; reason: retains the common-length equality from the source preamble as an explicit conclusion
- encoding: T_n = (39·3^n − 35)/2 → the equality cast to ℚ; reason: exact division, no natural-number truncation
Preamble
import Mathlib import Definitions.Def_TwoOptAllExp_TSP_Supplement_MCA232
Formal statement
namespace TwoOptAllExp.TSP.Supplement
open MCA232 MCA232.Vx
/-- **Observation 21** (p. 31). For `n ≥ 0`, the common length
`T_n = |Ω_n| = |Ω̄_n|` equals `(39 · 3^n - 35) / 2`. -/
theorem observation_21 (n : ℕ) :
(OmegaBar n).length = T n ∧ (T n : ℚ) = (39 * 3 ^ n - 35) / 2 := by sorry
end TwoOptAllExp.TSP.Supplement
Source
Heimann, Hoang and Hougardy, Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment, November 2, 2026 preprint, STOC 2027 submission #112, SHA-256 9ac9fdf5ac1be95dff40e95db1590649f15b4eeb94559413175c88f9a42bff60, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/112.pdf, Observation 21, p. 31