午夜学术新闻

理论计算机科学里一个非常著名的问题 3SUM

假设你有 n个整数，你希望判断其中是否存在三个数相加等于 0。

这个问题不难，O(n^2) 时间内解决（想想怎么做，最笨的方法也才需要 O(n^3) 时间！）。

长期以来，专家共识，将时间复杂度降到 O(n^{1.999999})是不可能的。据说只有一位数学家明确表示不相信这一点。

这种“困难性假设（3SUM Hypothesis）”被用来推出许多其他问题的困难性结果。

但现在情况不同了！

Claude 找到了一个O(n^{1.9992})时间算法，并给出了 Lean 形式化证明。

随后该算法被 Josh Alman 和 Virginia Vassilevska Williams 这两位细粒度复杂度（fine-grained complexity）领域的顶尖专家检查和消化，估计它有 99.99% 的概率是正确的。

也就是说，很多建立在3SUM 以O(n^2)为最优的经验理论都是错的。

另外这么一个看起来很简单的问题，需要76页的长文网页链接

——————

另外今天很多人都参与了下面的讨论

the "Hard Problem" in a nutshell:

1. atoms aren't conscious2. humans are made of atoms3. humans are conscious4. so at least one of 1-3 must be false

Panpsychists say 1 is falseDualists say 2 is falseIllusionists say 3 is falseMaterialists say 4 is false

最后，据说openai即将发布400份前沿数学的证明