GPT-5.6 Pro 仅凭 58 词提示推翻近 30 年图论猜想

一名研究者近日借助 GPT-5.6 Pro，仅用 4 条英文提示词、累计 58 个单词，便在图论领域推翻了一个存在了近 30 年的猜想——Dinitz-Garg-Goemans 猜想。AI 最终交付了反例图、四页证明证书、穷举验证程序、机器可读反例数据以及 LaTeX 源码，其中每个组合都能被逐一检查。

猜想在研究什么

Dinitz-Garg-Goemans 猜想是 1999 年由 Yefim Dinitz、Naveen Garg 与 Michel Goemans 在单源不可分流路由领域提出的经典问题。它要回答的是：当运输任务不再被允许拆分到多条路线（对应现实中的整车配送、整单履约），能否在保持原有可分流方案成本不变的前提下，将道路最高负载控制在「仅多出一批货」的范围内。

过去二十多年里，研究者只在该猜想的部分特殊情形取得进展，一般图结构上的结论始终悬而未决。

反例的具体构造

GPT-5.6 Pro 给出的反例是一张只有 7 个节点、9 条有向边的小图，包含一个公共起点与三个目的地，三批货物的需求量分别为 15、10、15。每批货物都有两条可选路线：一条成本为 0 但需与其他订单共享部分路段，另一条成本为 30、可独立完成。

若允许拆分，三批货物可部分走免费路线、部分走收费路线，总成本最低为 58。一旦要求每批货物整体选择一条路线，问题即陷入两难：

• 免费路线之间两两冲突：任意两批货同时选择免费路线时，都会使某段道路负载分别达到 25、30 或 40，而对应上限分别为 24、29 或 39，每次都恰好超出 1 个单位。
• 因此满足负载上限的方案中，最多只有一批能走免费路线，剩余两批只能选择收费路线，最低成本达到 60。

由于 3 个目的地各对应 2 种路径，总组合数为 $2^3 = 8$ 种，AI 给出的完整反例可被穷举验证：其中 4 种满足容量要求的方案成本均为 60 或 90，另 4 种更便宜的方案则全部存在道路超载。

仅靠 58 词的求解过程

整个过程由 Dmitry Rybin 在与 GPT-5.6 Pro 的公开对话中完成。首条提示词除附件外几乎全是自然语言，要求 AI 构造一个完整、无条件的反例。模型首轮建立线性规划验证框架，搜索数千个小型实例后承认未找到，并警告将阶段性构造包装成反例会得出错误结论。

第二轮 Rybin 仅补充一句「继续研究，找到一个完整、无条件的反例」，模型仍未成功。第三轮他要求模型先深入理解结构再制定策略，搜索范围缩小到一种仅含 24 种状态的路由结构，但仍差临门一脚。

直到第四条提示「部分结果已经够多了，让我们用一个完整、无条件的反例收尾」，GPT-5.6 Pro 才交付了最终的 7 节点反例图。

过程中模型也坦承，仅检查预设路线远远不够，必须穷举网络中所有可能出现的不可分流路径，提示词虽短，但判断每一轮结果尚不构成决定性反例、并拒绝提前收工，是求解得以成立的关键。

事件的意义

值得注意的是，这并非孤立现象。过去一周，AI 已在包括 Jacobi 猜想等多个长期悬而未决的数学猜想上给出反例或进展。在「作者应该算 Rybin 还是 GPT-5.6 Pro」这一问题上，沃顿商学院教授 Ethan Mollick 也公开提出讨论。事件再次表明，当前前沿模型在组合优化与反例构造类任务上，已具备初步的自主推理与自我纠错能力，但人类判断仍然在关键节点上不可替代。