OpenAI 昨日發布了 372 項重大數學成果，其中包括對 Subhash Khot 提出的「唯一遊戲猜想」（Unique Games Conjecture, UGC）的證明，以及 L=BPL（機率性對數空間等於確定性對數空間）等理論計算機科學的核心難題。這些成果由 OpenAI 最新的內部模型生成，該模型可能在未來幾個月內向付費 ChatGPT 用戶開放，但這取決於 OpenAI 安全委員會的建議。據報導，該模型在嘗試約 8,000 個長期公開數學問題後，解決了約 5% 的問題，平均每個問題僅需約 3 小時的 GPT-Pro 級別算力。部分證明附有 Lean 驗證憑證，但截至发稿時，尚無人類完全理解這些證明的內容，學術界正處於解讀與驗證的競賽中。

除了 UGC 和 L=BPL，其他重要成果包括：打破自 1960 年代以來的障礙，證明傅立葉變換和整數乘法可在低於 O(n log n) 的時間內完成（具體為 O(n log^0.9999999999999 n)）；解決了 Greg Kuperberg 與 Scott Aaronson 於 2007 年提出的「酉合成問題」（Unitary Synthesis Problem），證明對於任何 n-qubit 酉變換 U，存在一個經典預言機 A 使得 U 可在量子多項式時間內實現。然而，原文明確指出該證明並未提供有效構造預言機 A 的方法，且此結果與多數人預期相反，這意味著若缺乏有效構造方法，其在解碼霍金輻射等問題上的應用仍受限。此外還包括：證明奇偶校驗（Parity）不在 QAC0 中；證明了隨機查詢複雜度與量子查詢複雜度之間存在接近四次方的分離；證明了靈敏度與塊靈敏度之間存在超二次方的分離；證明了二維能隙哈密頓量的面積定律；證明了矩陣乘法可在 O(n^9/4) 時間內完成，且採用了與此前 O(n^2.373) 等結果完全不同的方法；證明了永久函數的行列式複雜度下界為 Ω(n^3)；提供了隨機多項式時間算法來近似計算一般圖中的完美匹配數量；以及證明了在有理數域上求解多項式方程的不可計算性。

值得注意的是，理論計算機科學中最困難的問題如 P≠NP、P=BPP 或 NEXP⊄P/poly 並未被解決。此外，在 OpenAI 發布成果的前一天，Virginia Williams 和 Josh Alman 發布了一篇預印本，解決了 3SUM 問題和全對最短路徑問題，推翻了半個世紀以來的猜想。該成果關鍵想法來自 Anthropic 的模型，但 Anthropic 採用了與 OpenAI 不同的策略，即給予 Virginia 和 Josh 撰寫並發布經過整理版本的機會，作為交換條件提供補償，而非直接發布未經處理的 AI 解決方案。

對於 UGC 的證明，理論計算機科學家 Dana Moshkovitz（Scott Aaronson 的妻子）指出，該論文寫作極差，充滿了令人困惑的內容，若不借助 AI 輔助幾乎無法閱讀。她形容該證明像是「迷幻狀態下寫出的東西」，大量引用先前工作卻未解釋為何在存在不可能性結果的情況下仍可使用。UGC 證明引入了一種全新的、帶有噪聲測試的奇怪代碼構造，並非傳統的長碼或短碼。儘管如此，Moshkovitz 感到被證明正確，因為她一直相信 UGC 為真。

事件背景

唯一遊戲猜想（UGC）由 Subhash Khot 提出，該猜想若成立，意味著許多最佳化問題即使僅尋求略優於半定規劃鬆弛的近似解，其計算複雜度仍為 NP-hard。L=BPL 是去隨機化理論中的重要猜想，斷定機率性對數空間與確定性對數空間等價。酉合成問題（Unitary Synthesis Problem）由 Greg Kuperberg 和 Scott Aaronson 於 2007 年提出，探討是否每個 n-qubit 酉變換都能透過經典預言機在量子多項式時間內實現。奇偶校驗（Parity）不在 QAC0 中是量子複雜度理論自 1999 年以來的重大開放問題。矩陣乘法複雜度長期以來是算法研究的焦點，此前已有 O(n^2.373) 等結果。有理數域上多項式方程的不可計算性問題，此前僅知整數域（Diophantine 方程）的不可計算性（即希爾伯特第十問題）。

社群觀察

評論者 ZeljkoS 指出，報導中隱藏的關鍵資訊是該模型解決了約 5% 的長期公開數學問題，並計算出每個解決問題約需 60 小時的算力成本。評論者 nostrademons 認為文章開頭關於孩子嘲諷母親的情節顯然是人類撰寫的，因為 AI 無法模仿這種特定的混亂風格。評論者 ks2048 和 bradley13 對 AI 生成證明的可讀性表示擔憂，引用 Dana Moshkovitz 的描述，指出論文寫作極差，充滿了令人困惑的內容，必須依賴 AI 輔助才能理解，這引發了對證明有效性的質疑。評論者 parksb 將解讀 AI 證明的過程比作軟體工程師閱讀混亂的 AI 生成代碼，認為這是無償且缺乏認可的工作。