3-sum 降到 n^1.999 让人担心数学「丑陋」?换个视角又美了

thomasahle · x · 2026-10-07

讨论近期算法复杂性理论的进展及其审美争论。背景:3-sum 问题被压到 n^1.999、乘法算法降到 n(log n)^0.999 这类「擦线改进」结果,让一些学者担心数学深挖下去不过是「square packing」式的 ugly bound,失去美感。

转发者引用一张(未展示的)图表反驳:换一个正确的视角,这些结果其实并不丑陋——「丑的结果只说明你选错了视角」。这是一场复杂性理论圈(Karp 问题相关)内有传播度的学理讨论。