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

來(lái)源：新智元

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

震驚！震驚！

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

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

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

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

高德納是誰(shuí)？

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

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

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

難倒算法祖師爺?shù)膯?wèn)題

被Opus 4.6攻克了

在論文開(kāi)頭，高德納這樣講述道：

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

他直言：

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

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

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

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

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

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

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

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

這道題，是一道看起來(lái)簡(jiǎn)單，但實(shí)際上非常復(fù)雜的圖論問(wèn)題。

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

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

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

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

因此，整個(gè)圖有m3個(gè)頂點(diǎn)，3m3條有向邊。

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

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

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

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

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

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

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

這就說(shuō)明：答案很可能存在！

那么，能否找到一個(gè)通用公式？

多次嘗試，Claude在做研究

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

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

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

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

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

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

接下來(lái)的十幾次探索，Claude基本都是在不斷試錯(cuò)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

而這篇「Claude’s Cycles」，也許會(huì)被視為一個(gè)起點(diǎn)。

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

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

高德納是誰(shuí)？不止計(jì)算機(jī)科學(xué)教父

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

Donald Knuth，美國(guó)計(jì)算機(jī)科學(xué)家，斯坦福大學(xué)名譽(yù)教授

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

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

當(dāng)時(shí)，他只有36歲，這個(gè)歷史記錄還沒(méi)有其他得主打破。

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

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

1968年出版第一卷第一版，至1976年，已賣出超過(guò)一百萬(wàn)冊(cè)。

比爾蓋茨曾評(píng)價(jià)這套書：

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

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

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

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

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

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

高德納為人風(fēng)趣。比如，他會(huì)獎(jiǎng)勵(lì)每一個(gè)找出他的著作中任何錯(cuò)誤的人，就能得到2.56美元，因?yàn)椤?56美分剛好是十六進(jìn)制的一美元」（256 pennies is one hexadecimal dollar）。

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

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

開(kāi)Vibe Coding之先聲

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

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

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

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

對(duì)他來(lái)說(shuō)，「文學(xué)編程確實(shí)是由TeX項(xiàng)目派生出來(lái)的最重要的東西」。

后來(lái)，高德納回憶道：

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

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

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

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

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

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

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

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

這不僅使所在班級(jí)奪冠（獎(jiǎng)品為一臺(tái)電視機(jī)和每人一塊Giant Bar），他個(gè)人人也贏得一付雪撬。

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

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

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

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

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

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

參考資料：

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+時(shí)代，互聯(lián)網(wǎng)思想（wanging0123)，

第一必讀自媒體