--- author: Best Partners TV date: '2026-11-02' guest: '' layout: post.njk source: https://www.youtube.com/watch?v=G88KlqS7Du4 speaker: Best Partners TV tags: - computational-complexity - formal-verification - sat-problem - theoretical-computer-science title: OpenAI 論文宣稱推翻指數時間假設及其對計算複雜性理論與科學界的影響 summary: OpenAI 與 NVIDIA 先後發布宣稱推翻「指數時間假設」（ETH/SETH）的論文與驗證，提出計算 K-CNF 滿足賦值數量的確定性演算法。該成果雖具亞指數理論突破，但巨大常數使其在實際中不影響安全性，同時引發學界對 AI 生成形式化證明的審查與接納爭論。 insight: '' draft: true series: '' category: ai-application area: tech-engineering project: [] people: - 大飛 - Impagliazzo - Paturi - Ryan Williams - 陶哲軒 companies_orgs: - OpenAI - NVIDIA - 麻省理工學院 - 人類數學協會 products_models: [] media_books: [] status: evergreen --- 大家好，這裡是 Best Partners，我是大飛。 ### 論文發布與震撼 10 月 26 日，OpenAI 發布了一篇論文，標題只有一句話：指數時間假設是錯誤的。正文共 67 頁，包含 3,977 行程式碼和超過 710,000 行的形式化證明程式碼。幾個小時後，NVIDIA 也發布了來自 Cloud 的獨立驗證，得出了相同的結論。這兩家公司通常是死對頭，但這一次，他們彷彿達成了某種協議，要從電腦科學的根基中拔出同一根支柱。 博士學生理論上肯定會立即產生一種反應：這是否意味著我們在過去 25 年裡撰寫的數百篇頂尖會議論文現在都毫無價值了？另一群人半夜從床上跳起來，慌忙打開交易應用程序，以為以太坊出了問題。 首先要澄清一點：這個 ETH 不是那個 ETH。被推翻的「指數時間假說」與加密貨幣領域毫無關係；它討論的是完全不同的問題：是否有更可能更快地計算某些問題？ 論文的摘要相當克制，指出對於任何固定的 K，它提供了一種確定性演算法，可以精確地計算多項式空間中任何 K-CNF 的滿足賦值的數量。請注意，這是精確值，並非粗略估計。 ### 門鎖比喻與 SETH 的奠基 要了解它的重要性，我們首先必須從鎖說起。想像你常在家中安裝的那種超級安全的門鎖。一百多年來，世界各地的鎖匠和物理學家都對它進行了研究；理論上沒有人能證明它是無法撬開的，然而幾十年來，一代又一代的竊賊都未能打開它。因此，安全界乾脆制定了一條規則：這把鎖絕對不可能靠人力打開。 在接下來的 20 多年裡，無數學者圍繞這條規則進行研究，撰寫了數百篇重量級論文——有些研究結構相同的金庫門是否堅不可摧，另一些則根據這條規則定義了安全設計標準。可以說，現代安全體系的整個架構都牢牢地建立在這個基礎上。 就在最近幾天，兩家公司的模型突然出現，把一張紙重重地摔在桌子上，宣稱「這把鎖無法被撬開」的假設是錯誤的——我們已經找到了繞過它的方法。在場所有人的第一個反應都是：那麼，今晚我的前門還安全嗎？ 專家在審查推導過程時，不禁擦了擦額頭的冷汗；機械公式完美無瑕，沒有任何漏洞，但這種繞過它的方法究竟是什麼？經過嚴格證明，如果一個小偷站在你的門前，不停地轉動鎖 100 億年，裡面的彈簧就會因金屬疲勞而彈開，發出咔噠一聲。 現在，證據確鑿：這把鎖永遠不可能打開的鐵律已被推翻。但這會影響你今晚鎖門睡覺嗎？實際上，一點也不。一般竊賊犯案只需幾分鐘；等他們轉動它 100 億年後，這場秀早就結束了。 所以，對於撰寫研究論文的人群來說，天真的要塌下來了；他們過去 20 年發表的所有文章的前提都基於同一個假設：這把鎖在任何時間範圍內都無法打開，因此它被證明了。既然這一假設已被推翻，那麼所有建立在這一假設之上的定理的基礎也在一夜之間被掏空了。 ### SAT 問題與指數時間假設 在計算機科學中，這個鎖的真正名稱是 SAT。你可以想像在你面前有一排開關，總共有 n 個，每個開關只能向上或向下撥動。假設你得到數百條電力規則，其中每條規則都要求三個特定開關的組合滿足某個特定條件。請找到一種能夠同時滿足所有規則的配置。 這個問題的困難在於，每增加一個開關，可能性就會倍增。三個交換器只有八種可能的配置，這看起來非常簡單。但是，當開關數量達到 300 個時，可能性將超過 10 的 80 次方，比整個可觀測宇宙中的原子總數還要多。即使把全世界的電腦連接起來，在宇宙終結之前也無法計算出答案——那麼為什麼每條規則要用三個開關呢？因為寬度為 3 足以表達幾乎所有的組合難題；晶片佈線或路線規劃等都可以轉換成這種形式。 因此，SAT 已成為 NP 完全問題的標準基準。研究所需時間相當於探究一整類問題的上限。 幾十年來，頂尖的頭腦一直在嘗試加快隨機局部搜尋的速度：從隨機分配開始，每次選擇一個未滿足的條件，隨機翻轉其中一個開關，並反覆嘗試，這可以將 SAT 的時間成本降低到 (3/4)^n。其他人則改變了方法，先進行邏輯推理來推斷新的條件，然後隨機地給開關賦值——盡可能地推理，必要時進行猜測。這促成了 PPSZ 演算法的誕生，該演算法隨著時間的推移不斷改進；基數從 2 被壓縮到 1.618，然後又壓縮到略高於 1.307，但無論如何壓縮，n 仍然在指數中，導致隨著規模的增長，時間複雜度急劇上升。 25 年前，在碰壁無數次之後，學者 Impagliazzo 和 Paturi 斷言，這種指數級增長是自然規律，沒有任何演算法能夠從指數中消除 n。雖然沒有人能夠證明這一說法，但整個領域都相信它。 他們對這種信仰的相信程度如何？從晶片佈局設計師到物流調度員。即使是圖論學家，只要他們能在論文中證明更快的演算法可以破解 SETH，他們就可以自信地宣稱他們的演算法已經達到了宇宙極限。為什麼編輯距離、最長公共子序列、動態時間規整、Fréchet 距離或正規表示式匹配的運行速度不能超過二次時間？他們都卡在了同一個地方。許多此類結論的依據正是這個假設。隨著樹寬的成長，參數化問題（如獨立集合和支配集）也有許多下界，這些下界也藉鑒了樹寬。 它之所以能得到如此廣泛的應用，是因為它使用了一種叫做稀疏化引理的工具，這意味著任何公式都可以分解成幾個稀疏公式而不會丟失任何解。因此，如果你能證明稀疏情況不可能更快，那麼一般情況也不可能更快；但如果這條路走不通，所有後續結論都必須重新審視。 原始 ETH 指出，在最壞的情況下，3-SAT 需要的時間約為 2 的 O(n) 次方，且該指數無法降低。更強的版本 SETH 更為嚴格，它指出，隨著寬度 k 的增加，任何演算法都無法將指數之前的係數推到 1 以下。因此，數百篇頂尖會議論文都是在此基礎上層層建構起來的，但一旦基礎被移除，其上的一切都自然而然地崩潰了。 ### 代數方法與演算法架構 那麼，人工智慧究竟是如何打開這把鎖的呢？實際上，它走了一條非常規的路：純代數學。 讓我們從論文邏輯中最違反直覺的部分開始：標準方法是直接逐一計算解決方案的數量，但 AI 的方法是繞過前端，首先在每個開關上放置一個多項式掩碼，並將整個問題重寫為具有參數的多項式。這個多項式具有這樣的性質：當參數為零時，它表示原始問題；但當參數為其他特定值時，問題會分解成互不干擾的小部分，每一部分都可以獨立求和。因此，只需要在幾個點上進行評估，然後使用拉格朗日插值法推導出零點的真實答案。這有點像測量身高；即使尺子沒有碰到你的頭頂，你也可以透過觀察影子來判斷它的高度。 為什麼這些小部分可以彼此獨立？它依賴一組巧妙的交換矩陣，將原本糾纏在一起的開關分成幾組。團體之間不直接溝通；它們僅透過最少數量的共享整數測量來傳遞訊息。一旦測量方法確定，每個組別就可以獨立求和，整體複雜度立即下降。 當然，矩陣本身也必須仔細選擇。這種替換由輔助有理矩陣支持；從單位矩陣中減去插值後，插值度必須足夠小，並且必須控制其非零元素的位置。只有同時滿足這兩個條件，才能讓被替換多項式的次數保持較低。本文第四章致力於證明此矩陣的兩個性質：一個是度界限，一個是稀疏結構。這部分本質上是純粹的線性代數，與直覺幾乎沒有聯繫，也是整篇論文中最難理解的部分。 在證明過程中，也採用了一個非常出乎意料的方法：在演算法的開頭，使用一組奇偶校驗來過濾掉明顯錯誤的賦值。這種構造借鑒了糾錯碼中的擴展圖，將位元放置在邊上，要求連接到每個頂點的位元滿足一個較小的線性碼，並利用圖的擴展來確保非零向量無法隱藏。所以，實際上，它是組合數學、編碼理論和代數數學工具的融合。或許正是這種混合風格，使得它最不像人類的作品。 本文的論述過程也很有趣：它首先處理最簡單的情況，即每個 switch 最多出現在三個子句中，因此相應的多項式的次數非常低，使得插值成為可能。一旦這一步驟確定下來，它就使用稀疏化將任意寬度和密度的輸入分解成許多這樣的稀疏公式，逐一計算並求和。先從最容易解決的問題開始，然後再逐步擴展到整體，這是理論計算機科學論文的典型寫作風格。 為什麼這個度數能被推得這麼低？我應該在這裡補充一點：因為出現次數是有限的——例如，如果每個條件的多項式至多是三次多項式——整個乘法表達式的總次數不會超過 3n。這個線性上限是整個方法發揮作用的前提條件。一旦階數暴增，插值所需的係數數就會急劇增加，成本也會迅速失控。 接下來，我們需要計算如何分割組，分割多少組，以及每組保留多少測量行。分組越多，單一分組的體積就越小，但所有分組的測量行總數不能超過與 n 成正比的值。每行絕對值的總和也必須有一個上限。只有平衡這些變量，才能將總插值成本控制在可控範圍內。 ### 時間複雜度邊界與理論推論 論文中給出的運行時間上限為 2 的 O 次方（n 乘以 loglogn 除以 logn 的平方根）。不要被這串符號嚇到；你只需要專注在分母中 logn 的平方根。半個世紀以來，人類一直停滯不前，無法在指數 n 以下放置任何東西。AI 終於增加了一個隨 n 緩慢增長的項目。 從數學角度來看，這一步跨越了指數時間和亞指數時間之間的界線。這條線的判定標準其實很簡單：只要指數表達式的成長速度比 n 慢，你就越過了這條線。讓我們用具體數字來更好地理解這一點。如果有 100 萬個開關，你最初需要計算 2 的百萬次方。現在，那一百萬已經減少到幾十萬了。雖然這仍然是一個天文數字，但從理論角度來看，跨越或未能跨越這條線是完全不同的另一回事。 表示這個上限還有第二種方法。當條件的數量與開關的數量成正比時（這是最常見的密集情況），指數部分可以縮小到 n 除以 logn 的平方根。這兩個版本之間的差異完全在於那個額外的 loglogn 因子。論文提供了兩種版本：一種是通用密度版本，另一種是固定密度版本。後者才是推動電路時實際使用的。 隨著版本倒下，加強版 SETH 和 GAP-SETH 也隨之倒下。五個假設像多米諾骨牌一樣一個接一個地倒塌了。在此過程中，人工智慧也拆解了機率版本，這意味著具有有限誤差的 ETH、SETH 和 GAP-ETH 也不再可行。 然而，僅僅達到 2 的 o(n) 次方是不夠的；標準多項式時間規約會抵消這一優勢。要推進所有 NP 完全問題，我們需要達到 2 的 n 次 o(1) 次方。論文正文中明確闡述了這一點。所以，它並沒有聲稱整個 NP 都變得更容易了；它只涉及這些特定假設。 論文中有一些被忽略的細節。首先，看看結果的性質：該演算法是確定性的，並且使用多項式空間，而不是隨機的幸運猜測。這兩個資格可不是擺設。在複雜性理論中，確定性演算法和隨機演算法在空間和指數空間方面具有完全不同的地位；兩者兼備將使論點更加有力。 讓我們詳細闡述電路方面，它指的是相對於 NP 而言，可在 2 的 o(n) 時間內判定的語言類。論文的結論是，對於這類語言，存在一個問題，需要至少 c 乘以 n 乘以 logn 的平方根閘，對於無限多個輸入規模都成立。這已經與演算法無關了；它的目的是確定電路在無法繼續存在之前可以縮小到多小的程度。它的起源可以追溯到十多年前威廉斯提出的一個定理，而現在，這個前提終於得到了證實。 進一步擴展，計算獨立集或有效圖著色的數量可以在 2 的 o(n) 時間內完成；完美匹配的數量需要 2 的 o(n + epsilon) 時間；對於最大割算法，我們可以得到亞指數時間近似值，誤差任意小，故障概率可忽略不計。 另一個晦澀的推論涉及具有輸出局部性的布林映射，其中也可以在亞指數時間內實現窮舉搜尋和精確性。它特別指出，這並不與現有的無條件下界相衝突，例如受限證明系統（如正規歸結）的指數下界，這些下界仍然成立。因此，加速的是演算法，而不是證明系統；這兩條發展路線互不干擾。 還有集合劃分問題的例子。每個元素都有一個開關來指示它被分配到哪一邊，並且每個集合都增加了兩個規則；在轉換後的公式中，開關的數量等於元素的數量。因此，對於固定的集合大小，這個問題也進入了亞指數時間的範疇。 ### 理論突破與現實防禦的差距 聽到這話，你可能會問：「那麼，鎖真的被打開了嗎？」 總的來說，它在數學意義上是開放的，但在實際意義上不是開放的。一些研究人員已將新公式與現有的最佳人類演算法進行了比較。在這些理論結果中，符號背後往往隱藏著巨大的常數，這些常數在解方程式時被省略了。 即使對所有常數採用最樂觀的估計，新演算法也只有在開關數量超過 10 的 79 次方，甚至超過 10 的 168 次方時才能勝過人類，而可觀測宇宙中基本粒子的總數僅為 10 的 80 次方。換句話說，除非你動用宇宙中的每一個質子和電子來解決這個問題，否則在人類可能遇到的任何情況下，這把鎖都將保持安全。 ### 學界反應與「數學 2.0」 雖然暫時安全了，但數學家們已經忙得不可開交。麻省理工學院電腦科學教授瑞安·威廉斯是早被聘請來審查這項證明的人員之一。在 10 月 27 日的一次採訪中，他指出，雖然有些步驟是常規的，但其他兩三個地方的推理看起來像是外星人寫的。正是這些章節讓他相信，整個理論計算機科學界需要坐下來一起研究這個問題。 有趣的是，就在 10 月初，當 IAMOOC 平台發布 700 多份 AI 生成的數學手稿時，威廉斯公開抱怨說，這本質上是對數學家的 DDoS 攻擊。結果證明，他是這次第一個加入評審團隊的人。仔細想想，他對這個領域並不陌生。早在 2016 年，他就使用了一種協議來反駁 SETH 的一個變體，該變體依賴於證明問題本身無法快速驗證。但這一次，應該被視為一場正面交鋒；它的性質完全不同。 隨後，最初提出 SETH 的兩位研究人員 Impagliazzo 和 Paturi 連夜工作了幾天，組建了一個獨立的同行評審小組，親自審查證據；我們應該很快就能得到結果。 如果我們拓寬視野，就會發現關於人工智慧的爭論早已蔓延到科學界。10 月 22 日，菲爾茲獎得主陶哲軒在他的部落格上發表了一篇長文，提出數學領域需要進入他稱之為「數學 2.0」的新階段。他的判斷很直接：人工智慧已經能夠在短時間內大規模地產生數學證明，但人類理解這些結果的速度卻遠遠落後。以前，一個數學問題可能需要數十年的研究才能有人給出答案，但現在人工智慧可以一次性給出數百個證明；人類需要多久才能閱讀和理解它們，這仍然是一個未解之謎。 有些數學家乾脆選擇與商業人工智慧公司劃清界線。一個名為「人類數學協會」的組織已經聚集了 108 名成員，他們承諾不會為商業人工智慧公司提供數學研究方面的勞動力或諮詢，也不會發表人工智慧生成的數學文章。其中，有 654 人更進一步，加入了所謂的 5AIP，承諾在研究中完全不使用人工智慧。 一方面，該型號在短短幾個小時內就能提供 710,000 行證明；另一方面，超過 1000 名研究人員簽字表示他們不會參與。這兩件事同時發生，或許比先前被推翻的假設更能反映我們目前的狀況。 回到我們開頭提到的鎖定：以太坊下跌之後，真正的衝擊在於 20 多年來累積的習慣。人們已經習慣於使用無法證明的假設來為成千上萬種演算法設定界限。是否更換鎖具取決於隨之而來的巨額帳單，但我們確實需要重新討論是否應該改變這些習慣。關鍵在於，當機器給出的證明需要人類花費數年時間才能理解時，我們究竟該如何確定它是否正確？ 這個問題或許比以太坊是否……更重要。