刚刚，Claude独立攻克图论猜想，仅用31步！算法祖师爷高德纳震惊发文

新智元报道

编辑：Aeneas KingHZ

【新智元导读】就在刚刚，Claude独立攻克了图论猜想，写《计算机程序设计艺术》的计算机泰斗高德纳彻底震惊了！这一次，AI在自动推理和解决创造性问题上，又达到了全新的里程碑。

震惊！震惊！

就在刚刚，Claude仅用31步，就独立攻克了未解的图论猜想难题。

写《计算机程序设计艺术》的算法祖师爷高德纳惊呼：「我不得不重新评估生成式AI在数学研究中的作用」。

在斯坦福的官网上，他本人发布了一篇原始论文。开头两个字，就是「Shock！Shock！」

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

高德纳是谁？

他是写出了《计算机程序设计艺术》（TAOCP）、发明TeX的图灵奖得主，算法界祖师爷。

《计算机程序设计艺术》是高德纳一生中最重要的事业，他写这本书的目的是「组织和总结所知道的计算机方法的相关知识，并打下坚实的数学、历史基础。

一个写了50年算法书的人，都开始认真看待AI的数学能力，那就说明：AI，正在进入人类最核心的智力领域。

难倒算法祖师爷的问题

被Opus 4.6攻克了

在论文开头，高德纳这样讲述道：

我昨天得知，一个我花了数周时间研究的未解问题，刚刚被Claude Opus 4.6——Anthropic公司在三周前发布的混合推理模型——解决了！

他直言：

看来我迟早得重新审视自己对「GenAI」的看法了。 得知自己的猜想不仅有一个漂亮的解法，同时还能见证自动推理与创造性问题求解方面的这一戏剧性进步，真是令人欣喜不已。

故事是这样的，《计算机程序设计艺术》这个系列，从上世纪60年代就开始写，现在已经出了5本。

在88岁的高龄，这位算法祖师爷还在继续写这套书。

他在书里准备了一道关于有向哈密顿循环的题，和朋友们证明了这道题的特殊解，想把它推广到一般情况时，却解决不了了。

结果，这道题被Claude Opus 4.6解决了。

更严谨的说法是，AI找到了一个漂亮的构造方法，而高德纳随后给出了严格的数学证明。

这篇论文也因此成为一个标志性事件——生成式AI，第一次被认真记录在数学研究的故事里。

难倒算法祖师爷的题长啥样

这道题，是一道看起来简单，但实际上非常复杂的图论问题。

先想象一个三维网格空间，比如一个m×m×m的立方体。

其中每个点都可以用(i, j, k)三个坐标表示，每个坐标都在0到m-1之间。所以，整个空间里一共有m³个点。

接下来我们规定，从每个点都可以沿三个方向移动：i增加1，j增加1，k增加1。如果超过m−1，就从0重新开始。 这就形成了一个环形空间。

按照高德纳在论文中的正式定义，就是从每个顶点有三条有向边，分别指向三个方向的「下一个」顶点。

因此，整个图有m³个顶点，3m³条有向边。

而哈密顿环，就是一条路径经过所有顶点，每个顶点恰好一次，最后回到起点。这就是一个经典的图论问题。

而高德纳提出的问题更难：不是找一条路线，而是要找到三条路线，并且满足每条都是哈密顿环，每条长度都是m³，三条环刚好覆盖所有边。

也就是说：每条边只能属于其中一条环。

原本，高德纳就是准备把这个问题写进《计算机程序设计艺术》的新章节。

为什么这个问题如此困难？原因就在于，每个点都有三条出边。如果要组成哈密顿环，就必须选择其中一条。所以在每个点，都需要做一个选择。

因此，问题规模达到了3^(m³)个！这几乎无法通过暴力搜索完成，因此，必须找到某种规律性的构造方法。

此前，高德纳已经解决了m=3的情况，他的朋友Filip Stappers又通过实验找到了4≤m≤16的解。

这就说明：答案很可能存在！

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

多次尝试，Claude在做研究

Filip把问题交给了Claude Opus 4.6，而且制定了一个严格的规则——每次运行程序后，都必须记录探索的进展。

有趣的是，Claude并不是突然灵光一现，而是经历了31次探索，过程非常像一个研究生在做研究。

第一步，它尝试了简单函数，试图用一个函数g(i,j,k) 决定每个点的方向。但是很快它发现，简单线性函数不行。

第二步，它开启了暴力搜索，尝试用深度有限搜索（DFS），但搜索空间太大，效率太低。

第三步，是二维分析。Claude发现，如果只看二维情况，可以找到一种「蛇形路径」。于是，它试图把二维思路推广到三维。

随后，它构造了一种类似Gray code的三维蛇形路径，但删除第一条路径后，剩下的结构很难分解。

接下来的十几次探索，Claude基本都是在不断试错。

关键突破：纤维分解

在第15次探索时，Claude提出了一个关键想法：fiber decomposition（纤维分解）。

它注意到，如果定义s = (i + j + k) mod m，那么所有边都会把顶点从s移动到s+1，这就意味着：整个图可以按s分成层结构。

这样，每一层都像一个二维网格，这就把问题大大简化了。

Claude随后尝试了随机搜索、模拟退火和回溯搜索，这些方法可以找到一些解，但仍然没有发现通用规律。

于是Claude得出结论——需要纯数学结构。

第31次探索，Claude找到规则

在第31次探索时，Claude终于提出了一套简单规则，核心仍然是s = (i + j + k) mod m。

然后根据s、i、j的情况决定是否增加i、增加j、增加k。论文中称之为「bump」规则。

规则大致如下：如果s=0，根据j的值决定移动方向。如果0

这样就生成一条完整的路径。

Claude用程序验证了：对于m=3,5,7,9,11，路径都成立。而且三条路径都是哈密顿环，所有边都被使用。

当然，Claude只是提出了构造方法，数学上还需要严格证明。

随后，高德纳证明，这条路径确实访问了所有m²个具有相同i值的顶点，然后依次覆盖所有i，最终形成长度为m³的完整环。

类似证明也适用于另外两条环，于是整个问题被解决了。

而且，高德纳还通过进一步研究发现，Claude找到的并不是唯一解。

实际上存在760种类似的分解方法，这些解都满足同样的结构。Claude只是找到了其中一个。

另外，Claude只解决了m为奇数的情况。

如果m是偶数，问题仍然没有通用解，甚至m=2已经被证明不可能，所以这个研究仍然没有完全结束。

最大的意义，并不在于解题

如果说这件事真正有意义的地方，不只是解题，而是AI解题的方式。

在这个过程中，Claude并不是猜答案，而是在重新表述问题，写程序，发现规律。这一过程，和人类研究非常接近！

几十年来，人们普遍认为，数学证明是AI最难进入的领域。

但这篇论文说明：AI已经开始参与真正的数学探索，

未来也许会出现新的研究模式——人类提出问题，AI探索结构，人类完成证明。

而这篇「Claude’s Cycles」，也许会被视为一个起点。

高德纳写《计算机程序设计艺术》，已经超过半个世纪了，这套书记录了人类算法思想的发展。

而现在，AI被写进了算法大师鼻祖的论文中。这，可能只是一个开始。

高德纳是谁？不止计算机科学教父

高德纳，原名叫Donald Ervin Knuth，1938年1月10日出生于美国密尔沃基。

Donald Knuth，美国计算机科学家，斯坦福大学名誉教授

高德纳是公认为算法分析「祖师爷」，现代计算机科学的先驱，在数个理论计算机科学的分支做出基石一般的贡献。

凭借对算法分析和程序设计语言设计的重大贡献，他斩获1974年图灵奖（计算机科学领域的「诺贝尔奖」）。

当时，他只有36岁，这个历史记录还没有其他得主打破。

颁奖词中特意强调：他所著的系列丛书《计算机程序设计艺术》（The Art of Computer Programming，TAOCP）为计算机编程艺术做出的杰出贡献。

1999年底，这本书被《美国科学家》（American Scientist）期刊列为20世纪最佳12部学术专著之一，爱因斯坦的「相对论」、 罗素和怀海德的《数学原理》等科学史上的重要著作并列必读经典。

1968年出版第一卷第一版，至1976年，已卖出超过一百万册。

比尔盖茨曾评价这套书：

如果你真自认为自己是一个好程序员，去读《计算机程序设计艺术》吧。 如果你读完了这套书，你一定要把简历发给我。

1977年，他为了让这本书的印刷更精美，决定开发排版系统。八年后，他带着TeX回归。

TeX是全球学术排版的不二之选，尤其是处理复杂数学符号

截至2025 年，已出版的卷册包括第1、2、3、4A和4B卷，未来预计还将发布更多卷册。

第1至5卷旨在阐述适用于顺序机器的计算机程序设计核心内容；第6卷和第7卷的主题则更为专门，但仍具重要意义。

顺便一提，他的中文名高德纳，是在1977年访问中国前，他的朋友清华姚班之父姚期智的夫人姚储枫给他起了这个名字。

高德纳为人风趣。比如，他会奖励每一个找出他的著作中任何错误的人，就能得到2.56美元，因为「256美分刚好是十六进制的一美元」（256 pennies is one hexadecimal dollar）。

水木有帖子汇总整理关于Knuth的18条八卦：

可以上下滚动的图片，转自：https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ

开Vibe Coding之先声

对高德纳而言，编程不仅是技术、科学，还是艺术。

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

排版系统TeX让他萌发了「文学编程」的概念——

文学编程范式不同于传统的由计算机强加的编写程序的方式和顺序，而代之以让程序员用他们自己思维内在的逻辑和流程所要求的顺序开发程序。

对他来说，「文学编程确实是由TeX项目派生出来的最重要的东西」。

后来，高德纳回忆道：

它不仅让我前所未有地更快地写和维护可靠性更高的程序，而且成为我自20世纪80年代以来的最大的快乐之源——它有时实际上是不可或缺的。

我做的其它一些大程序，比如MMIX元模拟器，用我见过的任何一种其它的方法论是无法写出来的。其复杂性让我有限的智能望而却步。

没有文学编程，我的整个事业规划就会轰然倒塌。……文学编程是你更上一层楼的必要工具。

完全可以说，Vibe Coding和文学编程一脉相承，不知道老爷子自己有没有体验过真正的Vibe Coding。

从神童到计算机科学全才

自小，高德纳就「聪敏绝顶」——

他8岁时，当时某糖果商举办了一项小学生益智趣味比赛，要求用「Ziegler’s Giant Bar」（分别为糖果厂名和出产的棒棒糖名）里的字母写出尽可能多的单词。

小高德纳假装胃疼宅家两周，依靠一部大字典列出了4500个单词，而裁判才掌握的2000个单词！

这不仅使所在班级夺冠（奖品为一台电视机和每人一块Giant Bar），他个人人也赢得一付雪撬。

他在凯斯理工学院的数学研究表现极为出色，以至于在他完成本科学业时，学院授予了他数学硕士学位。

1963年，他获得加州理工学院数学博士学位。

1963-1968年，他先后任加州理工学院助理教授、副教授。

1968-1992年，任斯坦福大学一系列正教授及冠名教授职位。

1993年至今，任斯坦福大学「计算机程序设计艺术」荣休教授（Emeritus）。

据统计，高德纳一生荣获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