AI 找到 30 年图论猜想的反例

AI 对一项长期存在的图论命题提出挑战

据报道，一项已有 30 年历史的图论猜想，因某个 AI 系统在数小时内生成了一个反例而告破。根据《New Scientist》的报道，AI 初创公司 Autokernel 联合创始人 Dmitry Rybin 使用 ChatGPT 5.6 Pro，寻找 Dinitz-Garg-Goemans 猜想的结构性反例。该猜想在组合数学和优化领域作为一个开放问题已存在数十年。

报道称，Rybin 总共使用了四个提示，总字数不到 60 个词，而模型在搜索了大约 5.5 小时后返回了一个可证明该猜想为假的构造。如果这一反例在专家审查下成立，这一事件将标志着一个快速演进中的新趋势中的又一重要时刻：AI 系统不仅在协助常规证明工作或符号推演，还越来越多地发现会改变既有数学问题状态的新对象。

这种变化之所以重要，是因为反例在数学中占据特殊地位。一个定理可以在许多特殊情形中经受多年检验，但只要出现一个有效例外，普遍性的主张就会崩塌。在依赖较小例子中的模式来建立直觉的领域里，找到第一个打破规则的对象，往往出乎意料地困难。这正是大规模自动化探索可能具有优势的搜索问题类型。

这个猜想原本想表达什么

Dinitz-Garg-Goemans 猜想属于图论，也就是研究由顶点和边构成的网络。New Scientist 用一个物流类比来解释这一主张。设想货物从仓库发往多个目的地。在问题的一种版本中，这些货物可以被拆分成更小部分并独立路由。该猜想提出，这种灵活的设置可以转换成另一种安排，在货物保持不可拆分的情况下完成，而不会增加总成本。

这类说法之所以吸引人，是因为它暗示复杂的现实世界优化有时可以被简化为更清晰、更易分析的形式。如果猜想为真，它就意味着可拆分与不可拆分流之间存在一座可靠的桥梁。但据报道的反例显示，这座桥并不总是存在。在这些网络结构的某些地方，禁止拆分确实会改变猜想所声称不会变化的经济性。

对于专业研究者来说，这并不意味着整个领域崩塌，而是意味着前沿更加清晰。研究者现在可以追问猜想在哪些地方失效，受限版本是否仍然成立，以及哪些图类仍能保持所需性质。一个错误的猜想往往能像一个正确猜想一样带来大量有价值的工作，因为它迫使学界用更精确的地图取代一个宽泛但不准确的原则。

为什么这个案例引发关注

部分反响来自提示词表面上的简单性。Rybin 在接受 New Scientist 引述时表示，他自己已经为这个问题思考了很多周。然而，文中描述的提示却极为简短：先要求找到一个突破性的反例，随后反复要求继续搜索。这种反差成为故事核心。人们关注的不只是 AI 参与了其中，还在于人机交互界面看起来如此普通，而底层计算搜索可能正在执行某种非平凡工作。

这种区分很重要。短提示并不意味着推理过程简单，而是意味着用户不必手工设计一个密集的形式化工作流，就能引导系统朝着有用的搜索方向前进。随着 AI 工具不断进步，瓶颈可能会从逐步指定每个动作，转向界定正确的数学目标、严格检查输出，并把机器生成的对象转化为研究共同体能够验证并继续推进的形式。

New Scientist 还指出，这是本周第二次有 AI 被认为推翻了一项长期存在的猜想。该文把新的图论结果与此前 AI 生成的 Jacobian 猜想反例并列，还提到一个据称在 5 月破解了 Paul Erdos 一项数十年旧猜想的 OpenAI 模型。综合来看，这些事件表明，当下并非一次性的奇闻，而是机器辅助数学加速发展的更广泛趋势的一部分。

为什么图论可能特别容易出现意外

York 大学的 Chris Bowman-Scargill 对 New Scientist 说，数学界有个流传的玩笑：图论里的每个猜想都是假的。这个笑话反映了真实的结构性挑战。在图论中，某些在小例子里看起来稳定的行为，只要增加一两个顶点就可能突然改变。这使得经验性的模式识别不如在那些低阶例子与更大结构更能对应的领域那样可靠。

在这种环境下，自动化系统天然有用。它们可以超出人类随手检查的范围，进行大规模枚举，并寻找那些乍看并不直观的奇特构造。数学家可能对某个命题为何应当成立有很好的概念性把握，而机器则可以不懈地测试这种直觉是否能在空间更陌生的角落里站住脚。

可能的教训并不是数学家会变得多余。相反，他们的角色会改变。人类仍然决定哪些问题重要，评估某个构造的意义，识别其成立的结构性原因，并把原始计算输出转化为稳健的数学叙事。但搜索环境正在变化。当机器能够更快、更频繁地给出决定性例子时，提出猜想本身也许会变得更有纪律，也更具对抗性，研究者会预期在一个想法诞生的更早阶段就接受更积极的机器检验。

接下来会发生什么

眼下最关键的问题是验证。只有在专家确认该对象确实在精确的形式条件下违背了猜想之后，一个所谓的反例才会真正改变数学记录。New Scientist 将这一结果呈现为重大进展，但其长期重要性仍取决于学界如何验证、解读并延展它。

如果这一结果成立，它将进一步强化许多研究者已经在努力消化的趋势。AI 正从助手走向发现型工作的协作者，尤其是在搜索空间庞大但成功条件明确的领域。数学是一个尤其醒目的测试案例，因为其输出原则上可以被精确检验。这使得它比许多其他智力领域更容易区分炒作与实质。

即便如此，社会层面的影响也可能大于这一个猜想本身。新一代数学家正在面对这样一种可能性：有价值的洞见，或许会从用自然语言提示、运行数小时并返回人类没想到去构造的对象的系统中出现。无论这带来的是不安、兴奋，还是两者兼有，它都标志着发现可能发生方式的一次重要转变。

本文根据 New Scientist 的报道整理。阅读原文。