Lance Fortnow 撰文回顾 3SUM、APSP 与 ETH 猜想在复杂性理论中的角色

Lance Fortnow 重刊旧文，解释 3SUM、APSP 与 ETH 等经典猜想在复杂性理论中的作用。3SUM 已知最优算法为 O(n²)，学界普遍猜想不存在 subquadratic 算法；其地位可类比 P≠NP。文章还以 OpenAI 与 Anthropic 近期数学证明成立为假设，讨论如何从历史视角理解这些证明问题。