GPT-5.6和Fable 5聯手，解決了一道懸置25年的數學難題。
微軟研究院首席研究員Dimitris Papailiopoulos，證明了一個多項式時間算法，能讓MIMO檢測精確命中最 大似然閾值。
作者表示，這個過程花了他整整七天。
(相關資料圖)
MIMO檢測是無線通信領域的一個經典問題，需要接收端從被噪聲攪亂的信號中，把發送端原本發出的信息完整還原。
統計上這種操作已經可以做到，但過去的方法，是窮舉搜索，耗費的時間是指數級的。
所以問題就變成，能不能不通過窮舉，利用快速算法實現還原。
2001年，Hassibi和Vikalo以為找到了突破口，但2005年這條路又被Jaldén和Ottersten證明走不通。
此后學界又先后試過半正定松弛、比特翻轉局部搜索、AMP、統計物理方法，最接近的結果也只能停在比理論門檻高一倍的地方。
25年，一波又一波學者輪番上陣，但誰都沒能啃下來。
01、25年來，只能靠窮舉
MIMO檢測，是無線通信里的一個基礎問題。
發送端把N個比特通過一個N×N的信道發出去，信道會把這些比特混在一起，還會疊加噪聲；
接收端手里只有一份被攪亂過的信號，要把發送端最初發出的N個比特，一位不差地找回來。
理論上有一個萬無一失的辦法，叫最 大似然檢測，也就是把所有可能的比特組合都算一遍，找出跟接收到的信號最匹配的那一個。
這種方法一定能找到正確答案，前提是你愿意等——N個比特意味著2的N次方種組合，N稍微大一點，窮舉就要算到天荒地老。
1989年，Sergio Verdú證明了這類問題在最壞情況下是NP-hard的，也就是不管用什么算法，都存在某些輸入讓計算量指數級爆炸。
但「最壞情況」說的是數學上刻意構造出來、專門為難算法的信道矩陣。
現實里的無線信道不是誰刻意構造的，它的每一次衰減、每一次噪聲都是隨機產生的，不會挑那些最難算的情況來為難接收端。
于是學界從2000年代初開始問一個更具體的問題——
如果信道是隨機產生的，只要統計上存在恢復原始比特的可能，是不是就一定能找到一個不需要窮舉的算法？
后來的研究給出了一條精確的分界線，當信噪比達到2logN，發送的比特能夠被完全恢復的概率趨近于1。
低于這條線，連最 大似然檢測本身都會開始出錯，這條分界線因此被稱為最 大似然閾值。
問題于是變得具體——能不能設計一個跑得快的算法，精確命中最 大似然閾值？
2001年，Babak Hassibi和Haris Vikalo以為找到了答案。
他們分析的是一種叫球形譯碼（sphere decoder）的算法。
這種算法先在接收信號周圍劃出一個「球」，只在球內的候選里搜索，球外的直接跳過，靠這一步壓縮搜索范圍。
Hassibi和Vikalo推導出這個算法的期望復雜度公式，結果看起來是多項式時間的。
如果這個結論成立，這道題基本就解決了。
但2005年，Joakim Jaldén和Bj?rn Ottersten把這個結論推翻了。
他們證明，在任意固定的信噪比下，球形譯碼的期望復雜度其實是指數級的，不是多項式的。
原因是要以不趨于零的概率把發送的信號包進「球」里，球的半徑必須跟著問題規模一起變大，球一旦變大，球內要搜索的候選數量也跟著指數級增長。
球形譯碼這條路走不通之后，學界轉向了各種近似方法——半正定松弛、比特翻轉局部搜索、AMP（approximate message passing）、統計物理里的方法。
結果，每一種都能給出漂亮的分析，但沒有一種被證明能精確匹配2logN這條閾值。
2020年，一種把離散問題放寬成連續優化問題來解的方法，叫box relaxation，拿到了當時最 好的嚴格證明結果，能在信噪比達到4logN時做到精確恢復，但復雜度依然是理論門檻的兩倍。
25年過去，統計上「能恢復」和用快算法「能恢復」之間，一直隔著這條鴻溝。
上周，這條鴻溝被填平了。
Dimitris Papailiopoulos和GPT-5.6、Claude Fable 5證明，一個只有兩步的簡單算法，同樣能在信噪比等于2logN時精確恢復全部比特，而且是多項式時間，只需要O(N3)次運算。
而且這篇論文證明的是一個雙向結果。
一頭證明了這個算法能在信噪比等于2logN時，信號能被精確恢復；另一頭則進一步證明，信噪比只要略低于2logN這個最 大似然閾值，連「笨辦法」最 大似然檢測也會開始失敗。
02、GPT-5.6和Fable 5聯手證明
Dimitris找GPT-5.6和Fable 5來試這道題，兩個模型很快分別給出了自己的證明思路，但接下來的打磨過程一波三折。
GPT-5.6的路徑用了一種叫AMP的算法，這是Dimitris一直沒能吃透分析方法的一類工具。
Fable 5給出的路徑不同，用的是「符號LMMSE，加貪心逐位翻轉」，一個業內實際在用、卻從沒被嚴格證明過的老算法。
兩條路徑都各自給出了完整的證明，聲稱能在信噪比2logN精確恢復。
Dimitris最終選擇了Fable給出的這條路，讓GPT接手檢查和修補里面的漏洞。
GPT把漏洞修好了，但修好之后的證明是一堵「符號墻」，變量指著變量，被指著的變量又指著更多變量，而且塞滿Dimitris看不懂的矩陣分析工具。
接下來的幾天，他反復讓兩個模型互相簡化對方給出的論證，唯 一的底線是，不管怎么簡化，最后都要保住2logN這個門檻。
除此之外，只要他自己能看懂，怎么改都行。
他還拒絕了用Lean做形式化驗證，原因也很抓馬，因為……他不懂。
Lean是一種能讓計算機自動檢查數學證明是否成立的工具，但要用它，得先把證明翻譯成Lean能讀懂的形式語言。
這道翻譯工作本身也可能出錯，而Dimitris不懂Lean，也就沒法檢查翻譯對不對。
總之折騰了一周后，他終于拿到了一份可以逐行手算核對的證明。
拆開看，這個算法只有兩個核心步驟。
第 一步，叫LMMSE取整。
LMMSE（linear minimum mean square error，線性最小均方誤差估計）是信號處理里的一種標準估計方法，先給出一個不是整數、連續取值的粗略猜測，再把每個坐標按正負號取整成+1或-1。
這一步不需要精確猜中每一個比特，論文證明的是，取整后的結果和真實發送的比特之間，漢明距離（兩個等長比特串之間不同的位數）只有o(N)。
也就是說，隨著N變大，猜錯的比特數占總數的比例會趨近于零。
第二步，叫貪心逐位翻轉。
這步從第 一步給出的猜測開始，每一輪檢查所有N個比特，找出翻轉哪一位能讓代價函數（衡量當前猜測和接收信號匹配程度的一個數值，越小越匹配）下降得最多，就翻轉那一位，然后重復這個過程。
問題是，這樣的貪心搜索憑什么能找到正確答案，而不是在中途卡在一個錯誤的地方不動？
為了回答這個問題，論文證明了兩件事。
第 一，在猜測起點周圍的一個范圍內，每一個還沒猜對的點，都至少存在一位翻轉能讓代價函數嚴格下降，而且下降的幅度有一個不趨于零的下限，不會隨著N變大而消失。
這意味著貪心搜索不會卡死不動，永遠能找到繼續往下走的一步。
第二，代價函數本身會隨著漢明距離（也就是猜錯的比特數）增大而增大。
這形成一道天然的護欄——搜索路徑就算中途某一步猜錯的比特數量暫時變多，代價函數也回不到起點，沒法翻越這道護欄跑到猜測范圍之外。
把這兩件事放在一起看，每一步至少能降低多少代價，除以起點距離最 優解總共差多少代價，就得到貪心搜索的算法復雜度，論文算出來的答案是O(NlogN)步。
貪心搜索有一條停止規則，那就是找不到任何能讓代價下降的翻轉時，就停下來。
前面已經證明，護欄內每一個猜錯的點，都還有至少一位翻轉能讓代價下降。
也就是說，只要還沒猜對，算法就一定能找到下一步該翻哪一位，不會停。
等真的猜對了，任何一次翻轉都只會讓代價變得更差，這時候才沒有能改進的翻轉可選，算法這才會停下來。
貪心搜索唯 一能停下的地方，就是真實發送的那個比特串。
算法最終只會停在真實發送的比特串上，證明也就完成了。Dimitris表示，這一整套論證過程，自己已經從頭到尾驗證過一遍。
03、作者簡介
Dimitris Papailiopoulos，現在是微軟研究院的首席研究員，同時是威斯康星大學麥迪遜分校電子與計算機工程系的副教授。
他早年的研究方向是信息論和編碼理論。
2009年，他還是博士一年級學生，寫下了第 一篇論文，并于次年發表，合作者是導師Alex Dimakis。
那篇論文用一種叫MCMC（馬爾可夫鏈蒙特卡洛，一種靠隨機采樣逼近答案的計算方法）的方法，嘗試解決MIMO檢測這道題，但沒有成功。
這次被GPT-5.6和Fable 5證明拿下的，正是同一道題。17年前那道讓他卡住的題，這次被他自己解開了。
