问题
度量 TSP：边权满足三角不等式的完全图，求最短哈密顿圈。NP-难；近似算法竞赛：Christofides 1976 的 3/2 近似统治 45 年，Karlin–Klein–Oveis Gharan 2020 打破为 3/2−ε（ε ≈ 10⁻³⁶）。猜想：存在 4/3 近似——与 4/3 硬度下界（ «无 « 更好 » 除非 P=NP»）精确相遇。
主要概念
亚多面体与 Christofides 的两条腿
下界 LP： «subtour elimination LP»（ «亚多面体 »）—— «每个 « 非平凡 » 子集的 « 出边 ≥ 2»»；其积分间隙（ «最优整数解 / 最优 LP 解»）的猜想值就是 4/3（ «亚多面体间隙猜想»）。Christofides： «最小生成树 + « 最小完美匹配 » 补奇度 + 「欧拉化」»—— «3/2» 由 «树 ≤ LP/... » 与 «匹配 ≤ OPT/2» 的 «两腿 » 加和。
KKO 破冰机
KKO 的机器： «随机采样 » 的 «Maxwell–Boltzmann » 型 «点分布 »（ «按 « 亚多面体 » 的 « 变分 » 权 » 抽 « 树 »）， «最大熵 » 分析给 «奇度 » 的 «改进匹配 »—— «ε» 的 «天文小 » 来自 « « 谱 » 论证 » 的 «长尾 »：机制上 «ε 可放大 »、 «放大 » 需 «技术 » 突破。
主要命题与证明
命题 1（Christofides 3/2，完整证明） 度量完全图上，Christofides 算法返回 ≤ 3/2·OPT 的圈。
证明 ①MST ≤ OPT（ «删圈得树 »）；②奇度点集 S（偶数个）的 «最小完美匹配 » ≤ OPT/2： «OPT 限制到 S» 给 «偶圈 » 覆盖（ «Hamilton 圈 » 在 S 上的 «访序 »）， «偶圈 » 可 «二分 » 成两个 «完美匹配 »， «小者 ≤ OPT/2»， «三角不等式 » 下 «匹配 ≤ 访序 »。树 + 匹配 = 欧拉多重图 ≤ 3/2·OPT， «捷径化 »（ «三角不等式 » 允许）得哈密顿圈。□
命题 2（4/3 硬度） 4/3 − ε 近似 ⟹ P = NP（ «L-reduction » 型归约，Cormode–... 与 Karpinski 系）。
进展与文献
Christofides 1976（ «Barest » 技术报告）；Wolsey 的 «1/2−ε» LP 分析线；Karlin–Klein–Oveis Gharan 2020（STOC/Annals 系）； «整数间隙 » 的 «特例 »： «图 TSP»（ «0-1 权 »）已被 Mömke–Svensson 与 Mucha 等压到 4/3（ «图版已解决 »！）； «asymmetric TSP» 被 Svensson–... 破到 O(log log log)（2020s）。开放核心：把 ε 放大—— «KKO 机器 » 的 «长尾 » 是 «技术 » 还是 «本质 »； «亚多面体间隙 4/3» 的独立证明（ «LP 侧 » 的 «干净 » 目标）； «图 TSP» 的 4/3 到 «一般度量 » 的 «桥 »。