剛剛僅用31步，Claude獨立攻克圖論猜想，僅用31步！算法祖師爺高德納震驚發(fā)文

來源：新智元

【導(dǎo)讀】就在剛剛，Claude獨立攻克了圖論猜想，寫《計算機程序設(shè)計藝術(shù)》的計算機泰斗高德納徹底震驚了！這一次，AI在自動推理和解決創(chuàng)造性問題上，又達到了全新的里程碑。

震驚！震驚！

就在剛剛，Claude僅用31步，就獨立攻克了未解的圖論猜想難題。

寫《計算機程序設(shè)計藝術(shù)》的算法祖師爺高德納驚呼：「我不得不重新評估生成式AI在數(shù)學(xué)研究中的作用」。

在斯坦福的官網(wǎng)上，他本人發(fā)布了一篇原始論文。開頭兩個字，就是「Shock！Shock！」

論文地址：https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf

高德納是誰？

他是寫出了《計算機程序設(shè)計藝術(shù)》（TAOCP）、發(fā)明TeX的圖靈獎得主，算法界祖師爺。

《計算機程序設(shè)計藝術(shù)》是高德納一生中最重要的事業(yè)，他寫這本書的目的是「組織和總結(jié)所知道的計算機方法的相關(guān)知識，并打下堅實的數(shù)學(xué)、歷史基礎(chǔ)。

一個寫了50年算法書的人，都開始認真看待AI的數(shù)學(xué)能力，那就說明：AI，正在進入人類最核心的智力領(lǐng)域。

難倒算法祖師爺?shù)膯栴}

被Opus 4.6攻克了

在論文開頭，高德納這樣講述道：

我昨天得知，一個我花了數(shù)周時間研究的未解問題，剛剛被Claude Opus 4.6——Anthropic公司在三周前發(fā)布的混合推理模型——解決了！

他直言：

看來我遲早得重新審視自己對「GenAI」的看法了。 得知自己的猜想不僅有一個漂亮的解法，同時還能見證自動推理與創(chuàng)造性問題求解方面的這一戲劇性進步，真是令人欣喜不已。

故事是這樣的，《計算機程序設(shè)計藝術(shù)》這個系列，從上世紀60年代就開始寫，現(xiàn)在已經(jīng)出了5本。

在88歲的高齡，這位算法祖師爺還在繼續(xù)寫這套書。

他在書里準備了一道關(guān)于有向哈密頓循環(huán)的題，和朋友們證明了這道題的特殊解，想把它推廣到一般情況時，卻解決不了了。

結(jié)果，這道題被Claude Opus 4.6解決了。

更嚴謹?shù)恼f法是，AI找到了一個漂亮的構(gòu)造方法，而高德納隨后給出了嚴格的數(shù)學(xué)證明。

這篇論文也因此成為一個標志性事件——生成式AI，第一次被認真記錄在數(shù)學(xué)研究的故事里。

難倒算法祖師爺?shù)念}長啥樣

這道題，是一道看起來簡單，但實際上非常復(fù)雜的圖論問題。

先想象一個三維網(wǎng)格空間，比如一個m×m×m的立方體。

其中每個點都可以用(i, j, k)三個坐標表示，每個坐標都在0到m-1之間。所以，整個空間里一共有m3個點。

接下來我們規(guī)定，從每個點都可以沿三個方向移動：i增加1，j增加1，k增加1。如果超過m?1，就從0重新開始。 這就形成了一個環(huán)形空間。

按照高德納在論文中的正式定義，就是從每個頂點有三條有向邊，分別指向三個方向的「下一個」頂點。

因此，整個圖有m3個頂點，3m3條有向邊。

而哈密頓環(huán)，就是一條路徑經(jīng)過所有頂點，每個頂點恰好一次，最后回到起點。這就是一個經(jīng)典的圖論問題。

而高德納提出的問題更難：不是找一條路線，而是要找到三條路線，并且滿足每條都是哈密頓環(huán)，每條長度都是m3，三條環(huán)剛好覆蓋所有邊。

也就是說：每條邊只能屬于其中一條環(huán)。

原本，高德納就是準備把這個問題寫進《計算機程序設(shè)計藝術(shù)》的新章節(jié)。

為什么這個問題如此困難？原因就在于，每個點都有三條出邊。如果要組成哈密頓環(huán)，就必須選擇其中一條。所以在每個點，都需要做一個選擇。

因此，問題規(guī)模達到了3^(m3)個！這幾乎無法通過暴力搜索完成，因此，必須找到某種規(guī)律性的構(gòu)造方法。

此前，高德納已經(jīng)解決了m=3的情況，他的朋友Filip Stappers又通過實驗找到了4≤m≤16的解。

這就說明：答案很可能存在！

那么，能否找到一個通用公式？

多次嘗試，Claude在做研究

Filip把問題交給了Claude Opus 4.6，而且制定了一個嚴格的規(guī)則——每次運行程序后，都必須記錄探索的進展。

有趣的是，Claude并不是突然靈光一現(xiàn)，而是經(jīng)歷了31次探索，過程非常像一個研究生在做研究。

第一步，它嘗試了簡單函數(shù)，試圖用一個函數(shù)g(i,j,k) 決定每個點的方向。但是很快它發(fā)現(xiàn)，簡單線性函數(shù)不行。

第二步，它開啟了暴力搜索，嘗試用深度有限搜索（DFS），但搜索空間太大，效率太低。

第三步，是二維分析。Claude發(fā)現(xiàn)，如果只看二維情況，可以找到一種「蛇形路徑」。于是，它試圖把二維思路推廣到三維。

隨后，它構(gòu)造了一種類似Gray code的三維蛇形路徑，但刪除第一條路徑后，剩下的結(jié)構(gòu)很難分解。

接下來的十幾次探索，Claude基本都是在不斷試錯。

關(guān)鍵突破：纖維分解

在第15次探索時，Claude提出了一個關(guān)鍵想法：fiber decomposition（纖維分解）。

它注意到，如果定義s = (i + j + k) mod m，那么所有邊都會把頂點從s移動到s+1，這就意味著：整個圖可以按s分成層結(jié)構(gòu)。

這樣，每一層都像一個二維網(wǎng)格，這就把問題大大簡化了。

Claude隨后嘗試了隨機搜索、模擬退火和回溯搜索，這些方法可以找到一些解，但仍然沒有發(fā)現(xiàn)通用規(guī)律。

于是Claude得出結(jié)論——需要純數(shù)學(xué)結(jié)構(gòu)。

第31次探索，Claude找到規(guī)則

在第31次探索時，Claude終于提出了一套簡單規(guī)則，核心仍然是s = (i + j + k) mod m。

然后根據(jù)s、i、j的情況決定是否增加i、增加j、增加k。論文中稱之為「bump」規(guī)則。

規(guī)則大致如下：如果s=0，根據(jù)j的值決定移動方向。如果0

這樣就生成一條完整的路徑。

Claude用程序驗證了：對于m=3,5,7,9,11，路徑都成立。而且三條路徑都是哈密頓環(huán)，所有邊都被使用。

當然，Claude只是提出了構(gòu)造方法，數(shù)學(xué)上還需要嚴格證明。

隨后，高德納證明，這條路徑確實訪問了所有m2個具有相同i值的頂點，然后依次覆蓋所有i，最終形成長度為m3的完整環(huán)。

類似證明也適用于另外兩條環(huán)，于是整個問題被解決了。

而且，高德納還通過進一步研究發(fā)現(xiàn)，Claude找到的并不是唯一解。

實際上存在760種類似的分解方法，這些解都滿足同樣的結(jié)構(gòu)。Claude只是找到了其中一個。

另外，Claude只解決了m為奇數(shù)的情況。

如果m是偶數(shù)，問題仍然沒有通用解，甚至m=2已經(jīng)被證明不可能，所以這個研究仍然沒有完全結(jié)束。

最大的意義，并不在于解題

如果說這件事真正有意義的地方，不只是解題，而是AI解題的方式。

在這個過程中，Claude并不是猜答案，而是在重新表述問題，寫程序，發(fā)現(xiàn)規(guī)律。這一過程，和人類研究非常接近！

幾十年來，人們普遍認為，數(shù)學(xué)證明是AI最難進入的領(lǐng)域。

但這篇論文說明：AI已經(jīng)開始參與真正的數(shù)學(xué)探索，

未來也許會出現(xiàn)新的研究模式——人類提出問題，AI探索結(jié)構(gòu)，人類完成證明。

而這篇「Claude’s Cycles」，也許會被視為一個起點。

高德納寫《計算機程序設(shè)計藝術(shù)》，已經(jīng)超過半個世紀了，這套書記錄了人類算法思想的發(fā)展。

而現(xiàn)在，AI被寫進了算法大師鼻祖的論文中。這，可能只是一個開始。

高德納是誰？不止計算機科學(xué)教父

高德納，原名叫Donald Ervin Knuth，1938年1月10日出生于美國密爾沃基。

Donald Knuth，美國計算機科學(xué)家，斯坦福大學(xué)名譽教授

高德納是公認為算法分析「祖師爺」，現(xiàn)代計算機科學(xué)的先驅(qū)，在數(shù)個理論計算機科學(xué)的分支做出基石一般的貢獻。

憑借對算法分析和程序設(shè)計語言設(shè)計的重大貢獻，他斬獲1974年圖靈獎（計算機科學(xué)領(lǐng)域的「諾貝爾獎」）。

當時，他只有36歲，這個歷史記錄還沒有其他得主打破。

頒獎詞中特意強調(diào)：他所著的系列叢書《計算機程序設(shè)計藝術(shù)》（The Art of Computer Programming，TAOCP）為計算機編程藝術(shù)做出的杰出貢獻。

1999年底，這本書被《美國科學(xué)家》（American Scientist）期刊列為20世紀最佳12部學(xué)術(shù)專著之一，愛因斯坦的「相對論」、 羅素和懷海德的《數(shù)學(xué)原理》等科學(xué)史上的重要著作并列必讀經(jīng)典。

1968年出版第一卷第一版，至1976年，已賣出超過一百萬冊。

比爾蓋茨曾評價這套書：

如果你真自認為自己是一個好程序員，去讀《計算機程序設(shè)計藝術(shù)》吧。 如果你讀完了這套書，你一定要把簡歷發(fā)給我。

1977年，他為了讓這本書的印刷更精美，決定開發(fā)排版系統(tǒng)。八年后，他帶著TeX回歸。

TeX是全球?qū)W術(shù)排版的不二之選，尤其是處理復(fù)雜數(shù)學(xué)符號

截至2025 年，已出版的卷冊包括第1、2、3、4A和4B卷，未來預(yù)計還將發(fā)布更多卷冊。

第1至5卷旨在闡述適用于順序機器的計算機程序設(shè)計核心內(nèi)容；第6卷和第7卷的主題則更為專門，但仍具重要意義。

順便一提，他的中文名高德納，是在1977年訪問中國前，他的朋友清華姚班之父姚期智的夫人姚儲楓給他起了這個名字。

高德納為人風(fēng)趣。比如，他會獎勵每一個找出他的著作中任何錯誤的人，就能得到2.56美元，因為「256美分剛好是十六進制的一美元」（256 pennies is one hexadecimal dollar）。

水木有帖子匯總整理關(guān)于Knuth的18條八卦：

可以上下滾動的圖片，轉(zhuǎn)自：https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ

開Vibe Coding之先聲

對高德納而言，編程不僅是技術(shù)、科學(xué)，還是藝術(shù)。

日常生活大概就像編程。如果你熱愛一件事，就能把美感融入其中。

排版系統(tǒng)TeX讓他萌發(fā)了「文學(xué)編程」的概念——

文學(xué)編程范式不同于傳統(tǒng)的由計算機強加的編寫程序的方式和順序，而代之以讓程序員用他們自己思維內(nèi)在的邏輯和流程所要求的順序開發(fā)程序。

對他來說，「文學(xué)編程確實是由TeX項目派生出來的最重要的東西」。

后來，高德納回憶道：

它不僅讓我前所未有地更快地寫和維護可靠性更高的程序，而且成為我自20世紀80年代以來的最大的快樂之源——它有時實際上是不可或缺的。

我做的其它一些大程序，比如MMIX元模擬器，用我見過的任何一種其它的方法論是無法寫出來的。其復(fù)雜性讓我有限的智能望而卻步。

沒有文學(xué)編程，我的整個事業(yè)規(guī)劃就會轟然倒塌。……文學(xué)編程是你更上一層樓的必要工具。

完全可以說，Vibe Coding和文學(xué)編程一脈相承，不知道老爺子自己有沒有體驗過真正的Vibe Coding。

從神童到計算機科學(xué)全才

自小，高德納就「聰敏絕頂」——

他8歲時，當時某糖果商舉辦了一項小學(xué)生益智趣味比賽，要求用「Ziegler’s Giant Bar」（分別為糖果廠名和出產(chǎn)的棒棒糖名）里的字母寫出盡可能多的單詞。

小高德納假裝胃疼宅家兩周，依靠一部大字典列出了4500個單詞，而裁判才掌握的2000個單詞！

這不僅使所在班級奪冠（獎品為一臺電視機和每人一塊Giant Bar），他個人人也贏得一付雪撬。

他在凱斯理工學(xué)院的數(shù)學(xué)研究表現(xiàn)極為出色，以至于在他完成本科學(xué)業(yè)時，學(xué)院授予了他數(shù)學(xué)碩士學(xué)位。

1963年，他獲得加州理工學(xué)院數(shù)學(xué)博士學(xué)位。

1963-1968年，他先后任加州理工學(xué)院助理教授、副教授。

1968-1992年，任斯坦福大學(xué)一系列正教授及冠名教授職位。

1993年至今，任斯坦福大學(xué)「計算機程序設(shè)計藝術(shù)」榮休教授（Emeritus）。

據(jù)統(tǒng)計，高德納一生榮獲100多項大小榮譽，包括：

參考資料：

https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf

https://valeman.substack.com/p/donald-knuths-30-year-problem-solved

https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ

https://mp.weixin.qq.com/s/PkrJnuvtrL0OCJXzRPCxxA

https://mp.weixin.qq.com/s/XIcafYS9PbNgE2cMYHfQ5w

為偉大思想而生！

AI+時代，互聯(lián)網(wǎng)思想（wanging0123)，

第一必讀自媒體