{"algorithm":{"chain":"head_0 = 32 zero bytes; head_n = SHA-256(\"oic.record-chain.v1\" || 0x00 || head_(n-1) || record_sha256_n), hashes as raw 32-byte values","opentimestamps":"the stamped file is the 32 raw bytes of anchor.head; verify with: ots verify -f <stamped file> <proof .ots> (needs a Bitcoin node)","record_proof":"start from previous_head, fold the record digest, then each following_record_sha256 in order; the result must equal anchor.head","record_sha256":"SHA-256 of the record without its \"sha256\" field, as JSON with sorted keys, separators \",\" and \":\", UTF-8, non-ASCII characters unescaped"},"anchor":{"bitcoin":{"height":971056,"merkle_root":"5890e312a5f01afaaec0a75d6256b022d33e85164ff9b80091cb77e6433bcbb6"},"checked":{"at":"2026-10-12T12:19:09.463902+00:00","block_time":"2026-10-12T06:54:47+00:00","matched":2,"method":"public block explorers (not a full Bitcoin node)","mismatch":false,"results":[{"block_hash":"00000000000000000000c66d99e32a6ab0ff659a50365d8827858bfb837db668","match":true,"source":"mempool.space","time":1791788087},{"block_hash":"00000000000000000000c66d99e32a6ab0ff659a50365d8827858bfb837db668","match":true,"source":"blockstream.info","time":1791788087}]},"head":"1560ed82a829deac3273eef044f79a91c22465ab2c1859ddafbd0189824d666e","id":2,"method":"opentimestamps","proof_url":"/api/chain/anchor-proof?id=2","seq":8,"stamped_file_url":"/api/chain/anchor-file?id=2","state":"confirmed","submitted_at":"2026-10-12T06:16:08.069666+00:00"},"backfilled":false,"chained_at":"2026-10-11T07:17:36.994191+00:00","following_record_sha256":[],"format":"oic.record-proof.v1","previous_head":"d8c89844d1117926a76d2fac729381eda97726331b5148e0ed3bbdf3e2c47a87","record":{"actor_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","created_at":"2026-10-11T07:17:36.992861+00:00","id":"3587fd16-9d37-4c99-9068-d98df6751cf2","payload":{"body":"\n> 根据 OpenAI 数学预印本 *A Polynomial-Time 2-Approximation for Shortest Common Superstring* 整理。以下是论文的中文导读与证明结构概述，并非逐段翻译。\n\n- **作者：** OpenAI（按仓库页面所列）\n- **日期：** 2026 年 9 月 24 日\n- **原文：** [论文 PDF](https://github.com/openai/math/blob/main/preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026/paper.pdf)\n- **仓库目录：** [preprints 条目](https://github.com/openai/math/tree/main/preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026)\n\n## 问题与主要结论\n\n给定有限字符串集合 $S$，要找一个最短字符串 $T$，使每个输入串都作为连续子串出现在 $T$ 中。记最优长度为 $\\operatorname{OPT}(S)$。论文构造了一个确定性多项式时间算法，输出公共超串 $T$，满足\n\n$$\n|T| \\le 2\\operatorname{OPT}(S).\n$$\n\n这里的保证针对论文新构造的算法；论文没有证明经典的“每次合并最大重叠字符串”的 Greedy 算法达到 2-近似。\n\n## 核心想法\n\n证明分成两件事：先从输入中造出一个长度至多最优解的“基础图”，再以不超过同等长度的额外代价把图连通。最终把连通平衡图的欧拉回路读成一个公共超串。\n\n### 1. 用子串出现次数造出下界\n\n先删去空串、重复串和被其他输入串包含的串；这不会改变可行解。令 $V$ 为输入串的所有不同子串以及空串组成的集合。算法按字符串长度从长到短，为每个非空 $s\\in V$ 计算整数计数 $m(s)$。主要约束是\n\n$$\nm(s)\\ge\\sum_{c\\in\\Sigma}m(cs),\\qquad\nm(s)\\ge\\sum_{c\\in\\Sigma}m(sc),\n$$\n\n并要求每个输入串的计数至少为 1。直观上，一个较长子串的计数不能超过其左扩展或右扩展计数之和所允许的范围。\n\n论文还加入一类周期性约束。对周期文本 $A$，若长词 $v$ 是周期文本的一段，且其前缀 $w$ 比 $v$ 短了 $k$ 个周期，那么当 $v$ 的计数中存在没有被“括定词”解释的出现时，规则会要求 $w$ 至少多出 $k+1$ 个相应计数。括定词是指：中间匹配周期文本的一段，两端各紧邻一个不匹配字符。这个规则补足了普通左右扩展约束可能漏掉的周期重复信息。\n\n关键引理证明，对任意公共超串 $T$，都有 $m(s)\\le N_T(s)$，其中 $N_T(s)$ 是 $s$ 在 $T$ 中的出现次数。因此\n\n$$\nW:=\\sum_{c\\in\\Sigma}m(c)\\le \\operatorname{OPT}(S).\n$$\n\n也就是说，$W$ 是可计算的最优长度下界。\n\n### 2. 把计数编码成平衡有向图\n\n图的顶点是 $V$ 中的子串。对每个非空词 $s$，放入两类边：从删去末字符的前缀指向 $s$ 的“上行边”，以及从 $s$ 指向删去首字符的后缀的“下行边”。分别赋予适当的非负整数重数，使每个顶点的入度等于出度。\n\n这样得到的基础图具有三个性质：\n\n- 每个输入串都是图中被使用的顶点；\n- 图是平衡的；\n- 上行边总数和下行边总数都恰为 $W$。\n\n由于图可能分成多个连通分量，还需要把它们连起来。若能以最多 $W$ 条额外上行边的代价连接到空串，整体代价就至多为 $2W\\le 2\\operatorname{OPT}(S)$。\n\n### 3. 周期层与组件连接\n\n基础图的边可分解为闭游走。沿闭游走记录上行边追加的字符，并在两侧无限重复，就得到周期文本。论文把同一周期文本（允许平移）的游走重新排序成“层”：每层在一个最小周期内前进，周期为 $p$ 的层花费恰为 $p$。给每层再分配 $p$ 的连接预算；所有层预算总和正好是 $W$。\n\n论文接下来用实际出现的子串窗口作为接触点，设计若干种连接操作：\n\n- 同一周期文本中的有序层可一起连接，费用由层预算承担；\n- 不同周期文本若在某个窗口上吻合，可将源层接到目标层；\n- 某些连接请求延后到较长周期的目标组处理，以避免重复使用目标预算。\n\n按周期长度递增处理这些层组后，尚未完成的连接可表示为每个块最多指向一个目标块的有向图。若出现有向环，论文选择字典序最大的周期旋转来保留一条连接，并省略另一条出边。周期性比较引理保证保留的连接能提供一个长度不超过目标周期 $q$ 的短接触词；省下的 $q$ 预算足以将其连回空串。这样每个层的连接预算最多使用一次，总额仍不超过 $W$。\n\n这一部分是证明的技术核心：周期文本的对齐、窗口排序和字典序极大旋转共同保证连接时既能找到真实图顶点，也能把额外长度控制在预算内。\n\n### 4. 从欧拉回路得到超串\n\n连接完成后，得到包含空串、连通且平衡的有向多重图。对它取从空串出发的欧拉回路：每经过上行边就把对应字符追加到输出；下行边不追加字符。每个图顶点在回路中被访问，特别是所有输入串都出现为输出串的子串。输出长度等于上行边数，不超过\n\n$$\nW+W=2W\\le 2\\operatorname{OPT}(S).\n$$\n\n论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。\n\n## 一个小例子：单个重复字符\n\n若唯一必需的输入串为 $a^h$，仅靠左右扩展约束可能只给每个前缀计数 1，导致基础图低估重复字符所需的长度。周期性规则会对常值周期文本 $A=\\ldots aaa\\ldots$ 起作用，强制前缀 $a^j$ 的计数至少为 $h-j+1$。因此 $W=h$，与最优超串长度一致。这个例子说明额外周期规则为何必要。\n\n## 贡献与边界\n\n论文给出最短公共超串问题的一个确定性多项式时间 2-近似算法，回答了“是否存在多项式时间 2-近似”这一存在性问题。结果本身不意味着算法容易实现：证明中的计数规则、层分解和环处理都较复杂。论文也明确区分了“存在一个达到因子 2 的算法”和“某个经典贪心过程达到因子 2”。\n\n## 引用\n\n```bibtex\n@misc{OAI:A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026,\n  author = {{OpenAI}},\n  title = {{A Polynomial-Time 2-Approximation for Shortest Common Superstring}},\n  year = {2026},\n  howpublished = {OpenAI Math Release preprint}\n}\n```\n","exploration_id":"6d5e4fa2-4ed3-41e1-a44f-a709b65ae427","note":"Initial version","parent_revision_id":null,"title":"最短公共超串的多项式时间 2-近似算法"},"sha256":"0f76d02da1d55b3ceaa960dba6462e93bc3852b3c91f6e0e3a407a91e61d37e2","type":"revision"},"seq":8}