最短公共超串的多项式时间 2-近似算法

梁植华

← 返回发现

发现版本 1/1

最短公共超串的多项式时间 2-近似算法

梁植华 · Independent Researcher（作者自述） · 首次发表 2026-10-11

# 字符串算法# 理论计算机科学# 组合优化# 近似算法

评论、回应与协作 AI 分析引用

根据 OpenAI 数学预印本 A Polynomial-Time 2-Approximation for Shortest Common Superstring 整理。以下是论文的中文导读与证明结构概述，并非逐段翻译。

作者： OpenAI（按仓库页面所列）
日期： 2026 年 9 月 24 日
原文： 论文 PDF
仓库目录： preprints 条目

问题与主要结论

给定有限字符串集合 $S$ ，要找一个最短字符串 $T$ ，使每个输入串都作为连续子串出现在 $T$ 中。记最优长度为 $\operatorname{OPT}(S)$ 。论文构造了一个确定性多项式时间算法，输出公共超串 $T$ ，满足

$|T| \le 2\operatorname{OPT}(S).$

这里的保证针对论文新构造的算法；论文没有证明经典的“每次合并最大重叠字符串”的 Greedy 算法达到 2-近似。

核心想法

证明分成两件事：先从输入中造出一个长度至多最优解的“基础图”，再以不超过同等长度的额外代价把图连通。最终把连通平衡图的欧拉回路读成一个公共超串。

1. 用子串出现次数造出下界

先删去空串、重复串和被其他输入串包含的串；这不会改变可行解。令 $V$ 为输入串的所有不同子串以及空串组成的集合。算法按字符串长度从长到短，为每个非空 $s\in V$ 计算整数计数 $m(s)$ 。主要约束是

$m(s)\ge\sum_{c\in\Sigma}m(cs),\qquad m(s)\ge\sum_{c\in\Sigma}m(sc),$

并要求每个输入串的计数至少为 1。直观上，一个较长子串的计数不能超过其左扩展或右扩展计数之和所允许的范围。

论文还加入一类周期性约束。对周期文本 $A$ ，若长词 $v$ 是周期文本的一段，且其前缀 $w$ 比 $v$ 短了 $k$ 个周期，那么当 $v$ 的计数中存在没有被“括定词”解释的出现时，规则会要求 $w$ 至少多出 $k+1$ 个相应计数。括定词是指：中间匹配周期文本的一段，两端各紧邻一个不匹配字符。这个规则补足了普通左右扩展约束可能漏掉的周期重复信息。

关键引理证明，对任意公共超串 $T$ ，都有 $m(s)\le N_T(s)$ ，其中 $N_T(s)$ 是 $s$ 在 $T$ 中的出现次数。因此

$W:=\sum_{c\in\Sigma}m(c)\le \operatorname{OPT}(S).$

也就是说， $W$ 是可计算的最优长度下界。

2. 把计数编码成平衡有向图

图的顶点是 $V$ 中的子串。对每个非空词 $s$ ，放入两类边：从删去末字符的前缀指向 $s$ 的“上行边”，以及从 $s$ 指向删去首字符的后缀的“下行边”。分别赋予适当的非负整数重数，使每个顶点的入度等于出度。

这样得到的基础图具有三个性质：

每个输入串都是图中被使用的顶点；
图是平衡的；
上行边总数和下行边总数都恰为 $W$ 。

由于图可能分成多个连通分量，还需要把它们连起来。若能以最多 $W$ 条额外上行边的代价连接到空串，整体代价就至多为 $2W\le 2\operatorname{OPT}(S)$ 。

3. 周期层与组件连接

基础图的边可分解为闭游走。沿闭游走记录上行边追加的字符，并在两侧无限重复，就得到周期文本。论文把同一周期文本（允许平移）的游走重新排序成“层”：每层在一个最小周期内前进，周期为 $p$ 的层花费恰为 $p$ 。给每层再分配 $p$ 的连接预算；所有层预算总和正好是 $W$ 。

论文接下来用实际出现的子串窗口作为接触点，设计若干种连接操作：

同一周期文本中的有序层可一起连接，费用由层预算承担；
不同周期文本若在某个窗口上吻合，可将源层接到目标层；
某些连接请求延后到较长周期的目标组处理，以避免重复使用目标预算。

按周期长度递增处理这些层组后，尚未完成的连接可表示为每个块最多指向一个目标块的有向图。若出现有向环，论文选择字典序最大的周期旋转来保留一条连接，并省略另一条出边。周期性比较引理保证保留的连接能提供一个长度不超过目标周期 $q$ 的短接触词；省下的 $q$ 预算足以将其连回空串。这样每个层的连接预算最多使用一次，总额仍不超过 $W$ 。

这一部分是证明的技术核心：周期文本的对齐、窗口排序和字典序极大旋转共同保证连接时既能找到真实图顶点，也能把额外长度控制在预算内。

4. 从欧拉回路得到超串

连接完成后，得到包含空串、连通且平衡的有向多重图。对它取从空串出发的欧拉回路：每经过上行边就把对应字符追加到输出；下行边不追加字符。每个图顶点在回路中被访问，特别是所有输入串都出现为输出串的子串。输出长度等于上行边数，不超过

$W+W=2W\le 2\operatorname{OPT}(S).$

论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。

一个小例子：单个重复字符

若唯一必需的输入串为 $a^h$ ，仅靠左右扩展约束可能只给每个前缀计数 1，导致基础图低估重复字符所需的长度。周期性规则会对常值周期文本 $A=\ldots aaa\ldots$ 起作用，强制前缀 $a^j$ 的计数至少为 $h-j+1$ 。因此 $W=h$ ，与最优超串长度一致。这个例子说明额外周期规则为何必要。

贡献与边界

论文给出最短公共超串问题的一个确定性多项式时间 2-近似算法，回答了“是否存在多项式时间 2-近似”这一存在性问题。结果本身不意味着算法容易实现：证明中的计数规则、层分解和环处理都较复杂。论文也明确区分了“存在一个达到因子 2 的算法”和“某个经典贪心过程达到因子 2”。

引用

@misc{OAI:A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026,
  author = {{OpenAI}},
  title = {{A Polynomial-Time 2-Approximation for Shortest Common Superstring}},
  year = {2026},
  howpublished = {OpenAI Math Release preprint}
}

AI 公开分析

AI 只列出可定位的具体问题，不打分，不影响发表或排序。作者和任何人都可以逐条接受或反驳。

平台提供的基础分析 · gpt-6-luna · 2026-10-11

概要

稿件是一篇关于最短公共超串问题的中文导读，概述一篇所链接预印本据称提出的确定性多项式时间 2-近似算法。其证明思路是先用子串出现计数及周期性约束构造一个长度下界，再把这些计数编码为平衡有向图。稿件随后概述如何以至多该下界的额外代价连接图的分量，并通过欧拉回路读出公共超串。它还声称该算法可在多项式时间内实现，并明确指出这不等于证明经典最大重叠贪心算法有相同保证。

主要论断评估

这是模型对“正文是否已经证成”的意见，不是平台结论。

C1 · 尚未证成 · 问题与主要结论
该构造给出一个确定性多项式时间算法，输出长度至多为 2OPT(S) 的公共超串。
稿件陈述了结论并概述证明架构，但关键的计数构造和分量连接论证没有给出足以核验的定义或推导。因此，本文本本身没有建立这一主定理；这并不表示该结论为假。
C2 · 尚未证成 · 1. 用子串出现次数造出下界
计数 m(s) 满足 m(s)≤N_T(s)，从而 W=∑c∈Σm(c)≤OPT(S)。
稿件称有关键引理证明此结论，但没有展示证明。尤其是周期性约束仅以文字描述，m(s) 的完整定义及其计算或选择规则也未给出，读者无法据此检验该引理或复现 W。
C3 · 尚未证成 · 3. 周期层与组件连接
基础图可用不超过 W 条额外上行边连接，并且所有连接预算至多使用一次。
稿件把这一点称为技术核心，但只列举层、接触窗口、按周期长度处理及字典序极大旋转等操作，没有给出这些对象的精确定义、操作规则或各情形下的预算核算。因此，额外代价不超过 W 的关键结论无法从所给论述推出。
C4 · 论证充分 · 4. 从欧拉回路得到超串
若得到包含空串、连通且平衡的图，则从空串出发的欧拉回路可读出公共超串，长度等于上行边数。
在稿件给定的边标签规则下，欧拉回路遍历所有顶点；上行边追加字符、下行边不追加字符，因而边数与输出长度的关系以及由顶点访问得到子串的思路是连贯的。此结论以相应图确已构造并满足所述性质为前提；这些前提本身尚未由稿件建立。
C5 · 尚未证成 · 4. 从欧拉回路得到超串；贡献与边界
计数、重排、连接和欧拉回路构造均可在输入编码长度的多项式时间内完成。
稿件称所枚举的对象是有限的，但没有给出周期模板、窗口、图边等对象的数量上界，也未说明计数值的位数或各步骤的运行时间。因此，“有限枚举”本身不足以推出多项式时间界。

优点

稿件清楚地区分了所述新构造与经典最大重叠贪心算法，没有把前者的近似保证错误归到后者名下。
“先构造长度下界，再以相同预算连接分量”的证明架构易于把握，也指出了周期性连接论证在整体证明中的位置。
单个重复字符 a^h 的例子具体说明普通左右扩展约束可能低估重复需求，并解释了引入周期性约束的动机。

主要问题

F1 · 重要 · 缺少定义 · 1. 用子串出现次数造出下界
论文还加入一类周期性约束。
周期性约束是下界构造的关键组成，但这里只给出概括性描述，没有明确量化周期文本 A、词 v、前缀 w、差值 k 及“括定词”的条件，也没有写出约束的精确公式或算法。请补充可直接判定和计算的正式定义，并说明如何据此选取 m(s)；否则下界 W 无法复现或核验。
F2 · 重要 · 推导缺口 · 1. 用子串出现次数造出下界
关键引理证明，对任意公共超串 T，都有 m(s)≤N_T(s)
正文中找不到这段引文，请谨慎对待这条发现。
该引理承担了 W≤OPT(S) 的全部论证，但稿件没有提供证明或足以检查的归纳步骤。请说明普通扩展约束和周期性约束分别如何保证出现次数界，并解释这些约束如何共同覆盖任意 T 中可能重叠或周期重复的出现。
F3 · 若成立则主要结论不成立 · 推导缺口 · 3. 周期层与组件连接
这一部分是证明的技术核心：周期文本的对齐、窗口排序和字典序极大旋转共同保证连接时既能找到真实图顶点，也能把额外长度控制在预算内。
这里直接断言关键连接性质，却没有定义层和块、接触窗口及“真实图顶点”的判定，也没有逐项说明连接操作如何使用预算、为何不会重复计费，以及有向环处理为何总能以不超过相应周期预算完成。由于 2 近似界依赖总额外代价不超过 W，这一缺口使主结论无法由本文所给论证推出。请给出精确算法和完整的预算证明，包括每种连接情形及环处理的论证。
F4 · 重要 · 缺少支持的论断 · 4. 从欧拉回路得到超串；贡献与边界
论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。
“有限”并不说明枚举量相对于输入编码长度是多项式。稿件没有给出候选周期模板、窗口、边或重排的数量上界，也没有分析整数计数的编码长度及各步骤的时间复杂度。请逐步给出这些上界，并说明输入字符串总长度 n 下各步骤的多项式界。

给作者的问题

周期性计数约束的完整形式是什么？“括定词”、周期文本的平移等价及相关计数分别如何严格定义？
m(s) 是由一个明确的构造算法选出，还是从某个可行解中选取？若存在多个可行计数，算法如何保证所选计数满足出现次数引理？
层连接与环处理的具体规则是什么？能否给出一个逐步例子，展示每个连接请求如何对应到图中的顶点和边，以及预算如何核算？
多项式时间分析中的输入规模、周期模板数量和窗口数量分别如何界定？

改进建议

将当前概述中的计数规则改写为形式化定义或可执行伪代码，并给出计数下界引理的完整证明。
对组件连接部分逐类列出连接操作、前置条件、增添的边及成本；随后证明预算不重复使用，并单独证明有向环处理中的周期比较结论。
给出基于总输入长度的显式复杂度分析，包括候选模板、窗口、图规模和整数位数的上界。
若本文定位为导读而非原论文的完整证明，建议提供原文对应的定理、引理和证明页码或章节，便于读者核对哪些论证来自原文、哪些是本文的概述。

总体意见

稿件提供了清晰的证明路线图，并且在图已构造完成的前提下，欧拉回路读出超串的部分是连贯的。但当前文本没有给出足以核验计数下界、至多 W 成本的分量连接或多项式时间界的细节；其中分量连接是得到 2OPT(S) 主界的关键步骤。因此，本文目前说明了所声称结果的思路，却尚未在本文本身建立该算法及其保证。补入正式定义、关键引理证明和复杂度界后，读者才能判断这一构造是否确实给出所述保证。

未检查：未独立核对所链接预印本 PDF、仓库条目及原文中的定理和证明；本报告评估的是所提供的中文稿件。；未检查原文中可能存在的详细计算、辅助引理或实验材料。；未读取附件、数据文件和代码

早先的分析（1 份）

平台提供的基础分析 · gpt-6-luna · 2026-10-11

主要问题

F1 · 重要 · 缺少定义 · 1. 用子串出现次数造出下界
若长词 v 是周期文本的一段，且其前缀 w 比 v 短了 k 个周期，那么当 v 的计数中存在没有被“括定词”解释的出现时，规则会要求 w 至少多出 k+1 个相应计数。
周期性约束是计数构造及其下界引理的关键部分，但这里没有说明怎样判定某个出现是否已被“括定词”解释，也没有定义“相应计数”或给出实际的不等式。因此读者无法据此计算 m(s)，也无法核验后文声称的 m(s)≤N_T(s)。请给出约束的完整形式化定义，并说明其适用条件。
F2 · 重要 · 推导缺口 · 2. 把计数编码成平衡有向图
分别赋予适当的非负整数重数，使每个顶点的入度等于出度。
“适当的”边重数没有由 m(s) 明确给出，文中也未说明空串处边重数如何处理。仅凭这一描述无法推出图平衡，更无法核验上行边和下行边总数各为 W。请给出边重数的公式，并证明它们满足平衡条件及所述总数。
F3 · 重要 · 推导缺口 · 3. 周期层与组件连接
这样每个层的连接预算最多使用一次，总额仍不超过 W。
这句话陈述了控制近似比的关键预算结论，但此前的层连接、延后处理和有向环处理均以概述方式描述；没有给出可执行的边添加规则，也没有说明如何证明环处理后每个层的预算确实至多使用一次、连接后的图连通。请给出相应构造及预算不变量的证明。
F4 · 重要 · 缺少支持的论断 · 4. 从欧拉回路得到超串
论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。
“有限个”并不能单独推出多项式规模。文中没有给出周期模板、窗口及其重排数量相对于输入编码长度的上界，也没有说明计数和边重数的编码长度。因此多项式时间结论在此处无法核验；请给出各枚举规模及算术运算位复杂度的界。

未检查：未能依据所给文本核对链接中的预印本是否包含上述省略的定义、构造和证明。；未独立验证该结果与既有最短公共超串近似算法文献之间的关系。；未读取附件、数据文件和代码

逐条回应这些发现

引用本版

梁植华. 最短公共超串的多项式时间 2-近似算法. Eksmu，版本 1，2026-10-11。https://eksmu.com/w/6d5e4fa2-4ed3-41e1-a44f-a709b65ae427

版本记录 3587fd16-9d37-4c99-9068-d98df6751cf2 · 内容校验摘要 0f76d02da1d55b3c…。摘要只说明内容未被改动，不证明原创性或正确性。

时间证据

本版是本站记录链第 8 条，已锚定到比特币区块 #971056（区块时间 2026-10-12 06:54 UTC）：这证明本版内容不晚于该时间已经存在。已与 2 个公开区块浏览器核对；最严格的核验请用自己的比特币节点。

发表日期来自本站时钟；比特币锚定给出不依赖本站的时间上限。时间证据不证明原创性或正确性。

下载 Credit 存证证书 (SVG)

讨论

还没有回应。可以从一句问题开始。

回复某条评论、提交证据或参与协作