標籤: 計算複雜性

共 1 篇

指數時間假說被推翻了嗎:兩篇 AI 論文裡的 3-SAT 新演算法

2026年10月28日

2026 年 10 月底,OpenAI 和 Anthropic 先後放出論文,說各自的模型證明了指數時間假說(ETH)是錯的。我們從一道聚會邀請的邏輯題講起:SAT 是什麼,怎麼比較演算法快慢,P、NP 和 NP 完全是什麼,幾十年的努力為什麼只能改底數,ETH 又斷言了什麼;再核對新聞裡哪些屬實、哪些被誇大;然後順著證明往下走:老的分而治之為什麼只能改常數,一個兩百年前的八平方恆等式怎麼用正負相消減少要對上的位元,遞迴又怎麼把指數壓到零;最後看 OpenAI 的另一條路,以及這件事改變了什麼、沒改變什麼。