Lior Pachter 借 OpenAI 论文重提 2015 编辑距离下界：生物学里 n 不会趋于无穷

lpachter · x · 2026-10-08

计算生物学家 Lior Pachter 在其系列帖第 3 条中，将其对 OpenAI 论文语料的批评与 2015 年 Backurs-Indyk 的（条件性）编辑距离下界相联系，并链接自己当年的博客文章《In biology n does not go to infinity》。

那篇 2015 年文章批评《波士顿环球报》对 Backurs-Indyk 结果的报道：该论文证明除非 SETH（强指数时间假设）为假，编辑距离无法在强亚二次时间内计算。Pachter 当时指出理论计算机科学的「最坏情况渐近结果」与生物学家实际关心的序列比对之间存在鸿沟——生物学中的序列长度并不会趋于无穷，这类复杂度下界对实际的 Needleman-Wunsch 场景意义有限。