AI 聲稱推翻 ETH：未等於 P=NP 或破解加密
OpenAI 公布三道數學問題的解答，其中一項聲稱推翻「指數時間假說」（Exponential Time Hypothesis，ETH）；其後 Anthropic 亦發布對 ETH 的獨立反駁。若證明成立，會動搖計算複雜度研究常用的一項假設，並迫使研究人員重看一批以 ETH 為前提的結果。
不過，這距離證明 P=NP，更不代表今日的加密服務已被破解，仍有很長距離。相關工作正由計算機科學界組織檢視，核心演算法及證明均要接受公開、逐步的專家驗證；MIT 教授 Ryan Williams 也引述 OpenAI 的評估指，該結果看來不會直接導致現有密碼系統失效。
ETH 說的是甚麼
P 與 NP 是理論計算機科學的基本問題。粗略說，NP 類問題的候選答案可快速核對；但能否同樣快速找出答案，則未有普遍結論。數獨是直觀例子：填好後可較快驗證，但由空白盤面找出解答往往困難得多。
許多密碼學設計依賴類似的不對稱性：持有密匙的人可有效率地讀取加密訊息，沒有密匙的人則面對在實務時間內難以完成的計算。不過，P 對 NP 的問題至今未解；主流直覺是 P 不等於 NP，而非已獲證明的定理。
ETH 是 1999 年提出、比 P 對 NP 更具體的假設之一。它主張，對某類邏輯滿足問題，即使採用最快演算法，隨變數數目增加，所需時間仍會呈指數式增長。研究者多年來以它作為下界假設：若 ETH 成立，便可說明某些問題不太可能有遠快於已知方法的演算法。
OpenAI 與 Anthropic 的主張，正是模型找到可在「次指數」時間處理這類問題的演算法。若論證無誤，反駁的是 ETH，並非直接得出 P=NP。Williams 認為，結果或會令研究者提高對 P=NP 可能性的估算，但不同人會有不同判斷；他也認為現有演算法未必已是最佳答案。
對加密的含意：先分清理論衝擊與即時風險
ETH 若被推翻，可能改變研究者判斷困難問題、設計演算法及建立複雜度下界的方式。過去十年不少論文把 ETH 納入前提，若新結果站得住腳，當中依賴該假設的推論需要重新檢視。
但「某類問題有較快演算法」不等於所有可快速驗證的問題都可快速求解，也不自動套用到某個實際加密方案。密碼系統是否受影響，要看新演算法針對的數學問題、實際運算成本、密匙長度及能否有效轉化為攻擊方法。根據報道，Williams 曾直接詢問 OpenAI 是否檢查過加密影響，而對方表示有檢查，並相當有信心結果不意味現有系統出現破綻。
因此，對一般使用加密通訊、網上銀行或雲端服務的人而言，現階段沒有理由把這宗消息理解為需要立即更換密碼或放棄加密服務。較合理的結論是：一項支撐研究推論的理論假設可能受到挑戰，實際安全後果仍須由密碼學界以具體攻擊模型和重現結果判定。
AI 交出證明後，人類怎樣驗證
這次事件也突顯 AI 參與基礎研究的驗證問題。數學與演算法證明的價值，不只在於得出結論，也在於每個定義、引理、化約和時間複雜度分析可讓別人審核。即使模型提出看似新穎的關鍵步驟，專家仍要檢查它是否暗中改變問題條件、漏算成本，或只在有限個案成立。
計算機科學界現正組成工作小組，並公開徵求意見；Williams 與 ETH 原始論文作者 Russell Impagliazzo、Ramamohan Paturi 協助解讀有關解答。Williams 指出，證明中有兩三個部分看來「陌生」，正因如此更需要整個社群共同檢驗。研究人員亦要求公開證明及討論 AI 貢獻的學術規範，並建議 OpenAI 資助會議。
這種做法的重要性在於可把 AI 的輸出由一次性公布，轉化為可重現、可質疑、可修正的共同知識。接下來要看的，是公開材料能否讓獨立研究者完整重現次指數演算法及其分析，以及其他以 ETH 為基礎的研究會否因而需要修訂。對軟件、AI 與密碼學研究者而言，這比單看「AI 解出難題」的標題更具實際意義。
延伸閱讀
AI 輔助說明： 本文由 AI 協助整理，並經兩輪獨立自動品質審核；資料及連結仍以原始來源為準。
參考來源
- TechCrunch — Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean? — original report
本文根據原文及公開資料整理；資料有出入時，以原文及官方資料為準。
