朋友問我：P=NP 被攻破了嗎？
朋友在群組丟來一則新聞，問我「P=NP 是不是被攻破了」。這則新聞是真的有東西，但朋友把兩件事混在一起了：被推翻的是 ETH，不是 P=NP。而且這次改善的是「上界」，不是「我們終於有快演算法」。這篇是把話講清楚的版本。
星期二晚上，朋友在群組丟來一張新聞截圖，問我：「這是說 P=NP 被攻破了嗎？」
我說：「不是 P=NP，是 ETH。」
他問：「那不是一樣嗎？」
那個當下我其實沒有好答案。隔天中午我們碰面，我花了半小時把這件事從頭講一次。這篇就是那次講的內容，加上後來我自己去讀原始手稿補上的細節。
那天到底發生了什麼
OpenAI 在十月六日先把七百多篇數學手稿放上 GitHub。十月二十六日又加了兩篇，其中一篇是目錄上的第 378 號：〈Disproof of the Exponential Time Hypothesis〉，論文自己的標題則是〈The Exponential Time Hypothesis is False〉。
整個庫現在是 721 篇手稿、373 個家族。家族編號有跳號，所以編號到 378，不代表真的有 378 個家族。
幾小時後，Anthropic 也說他們的模型在 10 月 16 日獨立找到核心想法，並稱 OpenAI 的模型「獨立且同時」證明了類似的結果。
朋友打斷我：「所以是誰先的？」
「不知道，也不重要。」我跟他說，真正值得看的地方，是這些東西還不是論文。
OpenAI 自己在 README 裡寫得很白：這些是「原始研究資料」，不是打磨過的學術論文，而且「部分沒有形式化的結果可能有問題」。整個庫大約 42% 的頂層結果有 Lean 形式化，這篇第 378 號是其中之一，核心的時間上界有被機器檢查過。
學界沒有急著下結論。Impagliazzo、Paturi（1999 年提出 ETH，期刊版 2001）跟 MIT 的 Williams 組了工作組、發公開信，特別強調一件事：參與，不等於認證。
到 10 月 28 日，MathWorld 的紀錄寫得很清楚：還沒有獨立驗證。
先從數獨開始
要講清楚這件事，得先講一個看起來完全不相關的東西：數獨。
朋友點頭，他玩數獨。
「你先想像一個填好的盤面。我拿給你看，你大概十秒就能確認對不對。但如果我給你一張空白盤，你要找到那組解，可能要半小時。」
這就是 P 與 NP 的差別。P 是「可以快速解」的問題，NP 是「答案可以快速驗證」的問題。
而 P 等於 NP 這句話的意思是：所有能快速驗證的答案，都能快速找到。
學界幾乎所有人都覺得這句話是錯的，但沒有人證明過。
ETH 比這句話更強。它不只是說「3SAT 不在 P 裡」，而是說：存在一個常數 c，使得 3SAT 至少要 2 的 cn 次方步。 3SAT 是這一類問題裡最標準的那一個，跟數獨同樣是 NP-完全。
打個比方。P 不等於 NP 只說「兩者不是同一個位置」；ETH 說的是「兩者至少相距兩千公里」——後者資訊多得多。
為什麼有人要假設這種東西
「假設一個沒人證明的東西，有什麼用？」朋友問。
用處在於：如果你知道兩地至少相距兩千公里，就可以推論沒有人能在一小時內開車到。 距離的下界，直接排除掉一整類「很快」的解法。
過去二十年，「細粒度複雜度」這個領域就是這樣運作的：先假設 ETH 成立，再證明「如果這個問題有快速演算法，那 3SAT 就有快速演算法，矛盾」。所以 ETH 不是課本上的名詞，它是一整批論文的地基。
那 OpenAI 到底做了什麼
他們的模型找到一個演算法，可以算出一個邏輯公式有幾組解——是「算出有幾組」，不是「判斷有沒有解」，比原本的要求更強。時間是 2 的 n 除以根號（自然對數 n）次方，空間則是多項式。
朋友指著我在紙上寫的那串式子：「這是什麼意思？」
「意思是指數還在，只是除以一個會慢慢變大的數字。n 越大，除得越多。」
「那不是變快了？」
「是。但要看跟誰比。」
目前最好的 3SAT 演算法（隨機化）大約是 1.307 的 n 次方。
假設 n 等於一千。那個等級的演算法，大約是 2 的 386 次方；這次的結果，大約是 2 的 380 次方。
只快了大約 60 倍。
60 倍聽起來不少，但 2 的 380 次方還是 10 的 114 次方。宇宙年齡以秒計，也只有 4 乘 10 的 17 次方。
真正的差別在 n 很大的時候。n 等於一百萬，一個是 2 的 269000 次方，一個是 2 的 386000 次方——差距拉開，但兩個都還是天文數字。
所以這次的重點不是「快多少」，而是「快過那條下界」。
上下界要分清楚
這裡有個容易搞混的地方。
演算法是一種「上界」：它告訴我們，這件事最多需要多少時間就能做到。
ETH 是一種「下界」：它說，這件事至少需要多少時間。
這次的結果，把上界壓到次指數。對足夠大的 n，這個上界會低於 ETH 宣稱的下界——所以 ETH 被推翻。
朋友問：「所以反過來也成立嗎？」
「你說的『反過來』有兩種。」
P 等於 NP 確實會讓 ETH 不成立——但那是同一個箭頭的逆否命題，不是新的推論。
真正不成立的是另一種反推：手上只有「ETH 被推翻」，推不出「P 等於 NP」。這個箭頭，不成立。
用回距離的比喻：原本大家以為至少兩千公里，現在證明只有八百公里。距離變短了，但你手上那台車還是太慢，一小時內到不了。
所以 P 是否等於 NP，到今天為止，完全開放。
那為什麼還是大事
「既然 P 等於 NP 沒有被動到，那大家在興奮什麼？」
「因為它拆掉了很多人的直覺。」
Ryan Williams 對媒體說，證明的有些部分也許算例行公事，但確實有兩三個「看起來很外星人」的部分，正是這些部分讓他覺得，這是整個社群要一起處理的課題。
他也說了一句很誠實的話：「每一位電腦科學家大概都該把 P 等於 NP 的可能性權重調高一點，但調整多少因人而異。」
「所以有人檢查過了嗎？」朋友問。
「有，但還沒檢查完。」
手稿裡大約 42% 的頂層結果有 Lean 形式化。Lean 是一套能讓電腦逐步檢查證明的工具。可是電腦檢查過，不等於結論成立——它確認推導沒有漏洞，卻不能保證題目定義是大家想的那一題，也不能保證這個定理有用。
實際影響大概三塊。
第一，細粒度複雜度要重看一批論文。那些「假設 ETH 成立，則某問題不能低於某個複雜度」的條件句，前提沒了；結論不一定變假，但不能再拿來推無條件下界。
第二，密碼學沒有因此被破。現行系統依賴的是因數分解、離散對數、格問題這幾類特定問題，不是 3SAT 這個家族；而且這次的演算法還是指數時間。
第三，工程上短期完全無感。任何拿這件事說「AI 推論要變快了」的說法，都是把理論上界當成執行時間。
回到那個群組
隔天吃完午飯，朋友問我最後一個問題：「所以這是假新聞嗎？」
「不是。」我說，「它有真東西。錯的是把它講成『攻破 P=NP』。」
「那我以後要怎麼看這種新聞？」
我想了一下，伸出三根手指。
「第一，看它是宣稱還是證明。發在 GitHub 上的手稿，跟期刊論文不是同一個等級的東西——更何況 OpenAI 自己就寫了『這是原始研究資料』。
第二，看它形式化到哪裡。Lean 能檢查推導，但不能保證題目是大家想的那一題。
第三，看它推翻了什麼、又沒推翻什麼。這次推翻的是『3SAT 至少要 2 的 cn 次方』這個下界的宣稱；它沒有推翻 P 不等於 NP，也沒有給出任何能用的演算法。」
他聽完，把手機收起來，說了一句：「所以那則新聞，是把『距離沒那麼遠』寫成『已經到了』。」
對。就是這樣。
這篇寫在 2026-10-29，學界審查還在進行中。如果後續出現獨立驗證、或證明被找出問題，我會回來更新。原始資料在 openai/math 的第 378 號家族；ETH 的定義與推論可以看 MathWorld。