高德纳：「震惊！震惊！」Claude破解《计算机程序设计艺术》难题

来源：市场资讯

（来源：机器之心）

编辑｜Panda

「震惊！震惊！」

是什么让著名计算机科学家和数学家、《计算机程序设计艺术》作者、图灵奖得主高德纳（Donald Knuth）发出了如此惊呼？

你没有猜错，正是 AI。

在他近期在斯坦福大学官网上公布的一篇论文《Claude’s Cycles》中，开篇的「Shock! Shock!」非常直白地表达了他对于 AI 强大能力的震惊。

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

紧接着他便写到：「我昨天得知，我已经研究了几周的一个开放性问题刚刚被 Claude Opus 4.6——Anthropic 公司三周前发布的混合推理模型 —— 解决了！看来我得在某个时候重新审视我对『生成式 AI』的看法了。不仅我的猜想有了一个不错的解决方案，而且这标志着自动推理和创造性问题解决领域的巨大进步，这真是一件令人高兴的事。我会在这篇短文中简要讲述这个过程。」

此事引发了广泛关注，网友们纷纷点评，感叹新时代的到来。

这是 Hacker News 用户 Ian Danforth 给出的太长不读版本：高德纳提出一个问题，他的朋友借助 Claude 进行了 30 多次探索，在人类的仔细指导下，Claude 最终编写了一个 Python 程序，能够为所有奇数找到解。高德纳随后为该方法撰写了证明，并对 Claude 的贡献感到非常满意。偶数情况仍是未解之谜（Claude 在这方面未能取得太大进展）。

困扰算法泰斗的图论难题

高德纳在为《计算机程序设计艺术》未来卷撰写关于有向哈密顿环的内容时，遇到了一个棘手的开放性问题。

具体而言，需要考虑一个具有 m³ 个顶点的有向图，顶点坐标记为 ijk，其中 0≦ i, j, k2 的情况。

高德纳此前已经解决了 m=3 的基础情况，并将其作为书中的一道练习题。他的朋友 Filip Stappers 随后通过实验发现了 4≦ m≦16 的解，这使得所需分解法存在的可能性极高。为了寻找通解，Stappers 将这个问题原封不动地交给了 Claude 处理。

31 步探索：AI 的解题逻辑

在交互过程中，Stappers 对 Claude 设定了严格的规则指令：

• 在运行完任何探测代码后，必须立即更新 plan.md 文件。

• 在记录完成之前，绝对不允许开始下一步的探索。

Claude 采取了多种数学工具进行尝试。它最初尝试了简单的线性与二次函数，但均未奏效。接着，它尝试使用暴力深度优先搜索，最终因为搜索空间过大而放弃。随后，它引入了「2D 蛇形分析」，并准确识别出该有向图是一个带有两个生成元的凯莱图（Cayley digraph）。

问题的突破发生在后半程的探索中：

• 在第 15 次探索时，Claude 引入了「纤维分解」框架，将问题转化为在坐标上选择算子的排列组合。

• 在第 25 次探索后，它自主得出结论，认为模拟退火算法虽然能找到解，却无法给出通用构造，此时需要纯粹的数学推导。

• 最终在第 31 次探索时，Claude 注意到每个纤维的选择仅依赖于单个坐标，并据此给出了一个具体的 Python 构造程序，成功得出了 m=3, 5, 7, 9, 11 的完美分解方案。

严谨的数学证明与偶数域的挑战

得出构造代码仅仅是第一步。Stappers 验证了 3 到 101 之间所有奇数 m 的情况，均获得了完美的分解方案。随后，高德纳接手进行了严谨的数学证明。他详细推导了生成的第一个环包含所有具备相同特征的 m² 个顶点，从而证实其长度确为 m³，是一个真正的哈密顿环。

高德纳进一步研究发现，在所有类似 Claude 生成逻辑的分解法中，恰好有 760 种对所有奇数 m>1 均有效的解。Claude 凭借自身推导准确找到了其中的一种。

目前，偶数 m 的情况依然悬而未决。

• Claude 在探索中曾找到 m=4, 6, 8 的解，但未能发现其中的通用规律。

• 当被要求继续攻克偶数情况时，Claude 陷入了困境，后续甚至无法正确编写探索程序。

• 另一位研究者 Ho Boon Suan 借助 gpt-5.3-codex 生成了处理大于 8 的偶数 m 的代码，并在高达 m=2000 的规模下测试成功。

• 但由于其模式过于复杂，目前人工证明其正确性的难度极大。

在 Hacker News 和 Reddit 等技术社区中，开发者们普遍认为这次事件的核心意义在于，AI 在数学辅助证明中展现出了自主更换探索工具、排查无效路径的能力。

正如高德纳在文末所感叹的那样，克劳德・香农（Claude Shannon）在天之灵若能知晓他的名字与此类进步联系在一起，定会感到骄傲。

Hats off to Claude!

AI 进军数学殿堂：从竞赛夺金到前沿探索

高德纳的惊叹并非孤例。事实上，在过去的一年多时间里， AI 在解决复杂数学和逻辑问题上已经取得了多个具有实质性意义的突破。

• 国际奥数突破：2025 年 7 月，Google DeepMind 发布的 Gemini（Deep Think 模式）在 IMO 试题评测中达到金牌标准成绩，取得 35 分，并能在接近正式考试条件下输出完整自然语言证明。与此同时，OpenAI 也披露其内部模型达到了类似水平，但官方认证与评测细节相对有限。

• 编程竞赛能力跃升：2025 年 9 月，OpenAI 和 Gemini 都声称达到了 ICPC 金牌水平，能够在严格时间限制内解决高难度算法问题。不过，这些成绩主要来自平行测试或基准评估，并非以正式参赛身份在 International Collegiate Programming Contest 中获得官方金牌。

• 从解题到科研协作：如今，AI 在科研中的角色显著增强。模型开始借助外部工具参与数学研究与问题验证，在复杂猜想与定理探索中发挥辅助作用。例如， GPT-5.2 借助外部工具，协助数学家解决了数个悬而未决的 Erdős 猜想，并得到了著名数学家陶哲轩的验证。部分系统已展示出生成研究草稿与进行结构化推理的能力。

驱动这些突破的核心机制也发生了改变。 AI 开始减少对单次快速生成的依赖。现在的模型普遍采用「测试时计算扩展」或「慢思考」策略。通过在推理阶段投入更多算力，模型能够并行探索多条解题路径并进行严格的自我验证。

展望未来， AI 与数学的结合将突破封闭环境下的标准化考题。随着自然语言理解力与形式化逻辑的深度融合，AI 将成为数学家与工程师身边得力的合作者，帮助人类共同攻克那些停滞多年的科学难题。