AI 改进复杂度证明遭质疑 ugly 常数？原作者称真实界远更紧

aran_nayebi · x · 2026-10-08

Craig Gidney 惊叹 AI 参与的复杂度证明结果离谱：3SUM 上界 O(n^1.9992)，整数乘法 O(n(lg n)^0.999…99984)。Konsti Wohlwend 回应称这些『丑陋』的 0.99999984 并非算法真实运行时间：为了让证明更简单，作者使用了像 2^50 这样完全任意的保守安全边界，类比只对 x≥99999 证明 1/x²>0 以避开奇点。他判断真实界可能收紧到 O(n·lg lg n) 这类『漂亮』形式，AI 论文的目标只是证明改进存在，而非给出完美界，未来数月会看到大量收紧工作。