结果族 128：A factor-two approximation for shortest common superstring · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
基因测序仪吐出一堆零散短串,想找一条最短的”总串”把它们都连着装下——像把几段重复的歌词并成一句最短的完整歌词,重叠部分只唱一遍。这个问题是 NP 难的;近似比从 1994 年的 3 一路缓降到 2.466、再到 2026 年的 7/3,这篇论文造出确定性多项式时间算法,首次保证长度不超过最优的 2 倍。
关键词卡片
看个具体例子
输入 @@M@@\{001,011,100\}@@:最短公共超串是 10011(长度 5),三条串分别落在第 1–3、2–4、3–5 格。
算法保证输出长度 @@M@@\le 2\times\mathrm{OPT}=10@@,这里恰好给出最优的 10011。注意:2 倍保证属于这个新算法,而不是经典的”每次合并重叠最大对”贪心——那个 1988 年的猜想至今未证,且贪心最坏情形已知至少 @@M@@9/4@@ 倍。
为什么值得关心
近似比在这个问题上卡了三十多年,整数 2 这道关口首次被多项式时间算法从上方触及;而且本主结果已通过机器证明验证。
已 Lean 形式化
第一级台阶
导读里”把重复歌词并成最短一句”的场景翻译过来：对象是一批显式给出的零散短串；操作是找一条总串，把每条短串都作为连续片段装进去，重叠部分只算一次；要求有两个——总串长度不超过最优值的两倍，并且算法要在多项式时间内确定性完成。
第二级台阶
用本科术语搭好舞台。层级图的顶点是所有输入子串（含空串）：向上边追加一个字母、费用记一，向下边删去首字母、费用记零。一个平衡（每个顶点入出度相等）、连通且访问全部要求串的边多重集，其欧拉回路逐边写下的字母就是一条公共超串，长度恰为上边总数。再引入强制出现次数 m(s)：对每个子串 s 给出一个整数，保证任何公共超串中 s 的出现次数都不少于它；全体单字母计数之和 W 因而不超过最优值。同周期文本的回路可重排成恰走一个最小周期的”层”，每层配一份等于其周期的预算。
第三级台阶
| 主定理在这样的语境下陈述：存在确定性算法，时间按输入总编码长度（含符号标签）多项式，对任意有限字符串族输出公共超串 T 满足 | T | ≤2·OPT。假设各有分工：字符串显式表示、标签按编码长度计费，使超大字母表与变宽标签也在多项式时间内成立。费用核算的骨架是：强制计数给出费用恰为 W 的平衡基础图，连接各层花掉的附加费用至多再花 W，合计 | T | ≤2W≤2·OPT。还要澄清一点边界：这个 2 只属于本文构造的算法——经典的最大重叠贪心另案处理，其 2 倍猜想已知遭遇至少 9/4 的反例。 |
对任意显式给出的有限字符串族，本文构造出确定性多项式时间算法，输出长度至多两倍最优值的公共超串，首次跨过”多项式时间 2-近似”这道悬了三十多年的门槛。
最短公共超串（shortest common superstring）问题：给定一组字符串，求把它们都当作连续子串包含的最短字符串，是数据压缩与序列拼接的经典问题。Tarhio 与 Ukkonen 在 1988 年提出猜想：每次合并重叠最大一对的贪心过程（Greedy）即可达到 2 倍近似。近似比从 Blum 等人 1994 年的 3 起，经 @@M@@5/2@@、@@M@@2+11/23@@、@@M@@(14+\sqrt{67})/9<2.466@@ 一路缓降，2026 年 8 月刚推进到 @@M@@7/3@@；同期另有预印本给出贪心最坏比至少 @@M@@9/4@@ 的反例。本文用全新算法首次给出 2-近似。
主定理：存在确定性算法，运行时间关于输入的总编码长度 @@M@@N@@（包括符号标签的编码）多项式，对每个有限字符串族 @@M@@\mathcal S@@ 输出公共超串 @@M@@T@@ 满足 @@M@@\len{T}\le 2\OPT(\mathcal S)@@。注意两点：该保证只属于本文构造的算法，而非经典贪心；时间按编码长度计费，对超大字母表、变宽标签同样成立。
证明在”层级图”（hierarchical graph）上展开：顶点是所有输入子串（含空串 @@M@@\eps@@），向上边追加字母、费用 1，向下边删首字母、费用 0。平衡（每点入出度相等）、连通且访问全部要求串的边多重集，其 Euler 回路写下的字母即公共超串，长度为上边总数。
先构造”强制出现次数” @@M@@m(s)@@：按长度递降取满足 @@M@@m(s)\ge\sum_c m(cs)@@ 及对称式的最小整数，要求串至少计 1；再加周期规则——相对周期文本 @@M@@A@@，”括住词”（bracketing word）是两侧各带失配字母的匹配区间，贡献记作 @@M@@B_A@@，若长词 @@M@@v@@（比前缀 @@M@@w@@ 长 @@M@@k@@ 个周期）的计数超过被括住量，则强制 @@M@@m(w)\ge B_A(w;m)+k+1@@。任何公共超串中 @@M@@s@@ 的出现次数不少于 @@M@@m(s)@@，故单字母计数之和 @@M@@W\le\OPT@@。这组计数给出费用恰为 @@M@@W@@ 的平衡”基础图”，但可能不连通。
再把基础图重排为”层”（layer）：回路上追加的字母双向重复生成周期文本，同文本回路可保边重排为恰走一个最小周期 @@M@@p@@ 的层，费用与预算各 @@M@@p@@，合计仍是 @@M@@W@@。长度控制靠两个周期性事实：一致段有界（Fine–Wilf 推论）与字典序最大旋转性质。
最后花预算连接。跨文本接触须落在同时符合两侧文本对齐的实际窗口（”记录”record）上；多数连接只花源层预算，需目标层出资的”请求”只发给周期严格更大的层，待处理该周期时一并结算。仅由源层出资的连接可能围成有向环：取环上 distinguished rotation 字典序最大者，最大旋转引理保证出现长度不超过目标周期 @@M@@q@@ 的接触词；令目标块放弃出边、内部合并，省下的预算恰好支付它到 @@M@@\eps@@ 的往返。附加费用至多 @@M@@W@@，总长 @@M@@\le 2W\le 2\OPT@@。
论文正文给出完整证明，第 7 节逐项核验确定性多项式时间实现；据任务元信息，主结果已有 Lean 形式化证明。本结果族目前仅此一篇手稿，无姊妹篇互相支撑；文中对贪心猜想的讨论（Shibata 的 @@M@@9/4@@ 反例）属旁引结论，未经形式化。OpenAI 官方声明”未经形式化的结果可能有问题”，本文主结果不在其列，但其余论述仍宜以形式化库与社区核验为准。
问 1：证明中最关键、也最脆弱的一步在哪里？
答：连接阶段的预算记账。基础图按强制计数分成各带预算的层后，跨层连接须落在同时符合两侧文本对齐的实际窗口上；需目标层出资的”请求”只发给周期严格更大的层，待处理该周期时一并结算。只由源层出资的连接可能围成有向环——环上取字典序最大的 distinguished 旋转，最大旋转引理给出长度不超过目标周期的接触词，令目标块放弃出边、内部合并，省下的预算恰好支付到空串的往返。这套”同一份预算绝不花两次”的簿记环环相扣，任何一处漏结算或重复结算，2W 的总账即破。
问 2：为什么强调”显式表示、按编码长度计费”？
答：时间界必须对超大字母表与变宽符号标签成立：若按字符比较免费计费，标签本身的读写就不多项式了。显式表示也排除了压缩输入下问题形态的变化。这一模型选择使定理对一切普通字符串族无条件成立。
问 3：相对距离图路线，真正新意是什么？
答：此前算法（Blum 等 3、Sweedyk 5/2、Mucha 2+11/23、Englert 等 2.466、2026 年的 7/3）都走输入串上的距离图加最小权圈覆盖，难点在开圈连接的附加长度失控。本文改用全子串层级图（承 Golovnev–Kulikov–Mihajlin 与 Collapsing 框架），下界改用强制出现计数 W 而非圈覆盖，周期性工具（Fine–Wilf 一致段有界、字典序最大旋转）虽有 Breslauer–Jiang–Jiang 与 Mucha 的先例，但作用对象完全不同。
问 4：AI 生成证明最可能在哪里出错？
答：组合记账的边角——每条连接由谁出资、何时结算、环上最大旋转的接触词界、以及周期规则（括住词贡献 B_A 与周期数 k 的不等式）这些分支情形的完备性，正是机器证明最易漏一两种布局的地方。好在主结果已有 Lean 形式化兜底；但文中旁引的 Shibata 贪心 9/4 反例属外部预印本结论，不在形式化之列。
问 5：这个结果等于证明了贪心猜想的 2 倍吗？
答：不是，摘要与引言都明确切割：保证只属于本文构造的算法。经典 Greedy 猜想（Tarhio–Ukkonen 1988）针对每次合并最大重叠对的程序；按引用的 2026 年 9 月预印本，该程序最坏比至少 9/4，猜想已被反例击中。整数关口 2 是被新算法从上方触及的。
问 6：谁会用，还能再往下压吗？
答：数据压缩与 DNA 序列拼接是经典下游，层级图表示对相关字符串合并问题有迁移潜力。至于 2 以下：论文未讨论改进空间与硬度障碍的间距——SCS 已知的 NP-难下界远低于 2，2−ε 是否可达仍是公开战场。
总评
三十年的整数关口 2 被一个全新组合框架拿下，且有形式化背书，分量扎实；最大残留不确定性不在主定理，而在周边旁引结论与该框架向更小因子的延展空间。