《The Mathocalypse》: OpenAI 发布 372 项结果, 据称含 Unique Games Conjecture 证明

摘要

这篇个人记述称，昨日 OpenAI 发布了 372 项重大结果，其中包括在 Timothy Gowers、Edward Witten 等数学家推荐下给出的 Subhash Khot 的 Unique Games Conjecture（UGC）证明；若成立，许多优化问题即便只求略优于半正定规划松弛的近似也属 NP-hard。作者强调目前只是“相当确信”它是证明：部分结果有 Lean 证书，并非全部；似乎还没有人类理解这些证明，验证竞赛才刚开始。Dana Moshkovitz 形容论文极难读、需 AI 辅助，UGC 证明发明了带噪声测试的怪异递归码，既非长码也非短码；另有绕过 UGC 的 Max Cut 与所有 CSP 的最优 NP 硬度近似证明。