OpenAI 的 3SAT 亚指数时间证明，变量数须超过可观测宇宙原子数

paraschopra · x · 2026-11-14

Paras Chopra 分享一个反直觉发现：OpenAI 近期声称的 3SAT 亚指数时间算法，只有在变量数超过约 10^(2×10^10)（一个 200 亿位的数）时才优于暴力枚举，而击败当前最优 3-SAT 算法则需要变量数超过约 10^(3.5×10^11)。作为对比，可观测宇宙的原子总数仅约 10^80。也就是说，对任何物理上可能存在的输入规模，该算法都退化为暴力搜索或已知最优指数算法。论证出自 Ben Recht 在 arg min 博客的文章，文中借 Edmonds 1965 年关于「高效算法」定义的历史，批评复杂性理论中脱离原始问题的数学脚手架现象。