图论领域一个存在近 30 年的 Dinitz-Garg-Goemans 猜想，最近被 GPT-5.6 Pro 找到了反例。公开记录显示，研究者 Dmitry Rybin 在整个论证过程中一共输入了 4 条提示词，总计 58 个英文单词，最终拿到的是一张示意图、4 页证明证书、精确穷举验证程序、机器可读的反例数据，以及 LaTeX 源码。
这条结果指向的结论很直接：Dinitz-Garg-Goemans 猜想是错的。
这道猜想讨论的是单源不可分流问题。若把它放进一个更直观的场景里，可以理解成一座仓库向多个目的地送货。允许分流时，同一批货可以拆开走多条路线；但在不可分流规则下，每一批货都必须完整走一条路径，不能拆分。
这类问题并不只存在于数学模型里。网络数据、物流订单、交通调度和供应链分配里，都可能遇到类似约束：理论上的最优方案可以拆成很多小份，现实中的一辆车、一个订单却不能被切成 0.37 份。
一旦禁止拆分，可分流场景下的最优方案就很难原样照搬。原本分散在多条路径上的负载，需要整批转移到某一条路线，部分边上的负载可能随之上升。于是问题变成：怎样把“可拆分运输”的方案，改成“必须整批运输”的方案，同时又不让道路负载增加得过于离谱。
猜想研究的核心约束
1999 年，Yefim Dinitz、Naveen Garg 和 Michel Goemans 发表了单源不可分流领域的经典论文，证明在这类转换过程中，拥堵可以被控制在一定范围内。
但“不会堵得太严重”之外，还有另一层约束：成本会不会上升。随后，组合优化领域学者 Goemans 提出了一个更强的带成本版本，也就是后来的 Dinitz-Garg-Goemans 猜想。它要求在保持前述超载上限的同时，总成本也不应高于原来的可分流方案。
用更直白的话说，如果原本允许拆分时，既能做到成本低、又不会太堵，那么改成每一批货都必须完整走一条路线后，理论上也应该能找到一个同样便宜，并且最多只多堵一批货的方案。
这个看上去很符合直觉的猜想，在一般图结构上一直没有被证明，后续研究只拿下了部分特殊情形。很多年里，它既没有被完整证明，也没有被推翻。
反例如何击穿猜想
GPT-5.6 Pro 给出的反例，正好卡住了猜想要求同时成立的两件事：负载不能超出规定上限，成本又不能高于可分流方案。
这个反例构造了一张只有 7 个节点、9 条有向边的小图，包含 1 个共同起点和 3 个目的地。3 批货物的需求量分别是 15、10 和 15。每一批货都有 2 条可选路径：一条路径成本较高，每个订单走完需要花费 30；另一条路径成本为 0，但要与其他订单共享部分道路。
在允许拆分的情况下，这 3 批货可以分别把一部分走收费路径、一部分走免费路径，最终总成本是 58。
问题出在不可分流约束上。GPT-5.6 Pro 给出的结论是，这 3 个“免费选项”之间存在两两冲突。任意两批货如果同时选择免费路径，都会在某一段道路上形成共同拥挤，使实际负载达到 25、30 或 40，而对应道路允许的上限分别只有 24、29 和 39。
也就是说，每一次都恰好超出 1 个单位。
这意味着，如果要守住猜想规定的负载上限，3 批货里最多只能有 1 批走免费路径，剩下 2 批必须走收费路径。由于每批收费路径的成本是 30，因此任何符合负载要求的方案，最低成本都是 60。
矛盾也就由此形成：想把道路负载压在规定上限内，成本最低是 60；想把成本压回原来可分流方案的 58，就至少会有一条道路超标。而猜想原本断言，这两个条件可以同时满足。
穷举验证只有 8 种组合
这组反例的验证过程并不复杂。3 个目的地各有 2 种路径，总共只有 2^3=8 种组合。
把这 8 种可能逐一列出后，可以看到其中 4 种满足容量要求，成本分别是 90、60、60 和 60；另外 4 种虽然更便宜，但都存在道路超载问题。
按文中说法，所有情况都可以穷举检查，不存在遗漏的隐藏路径。只要这张图的定义与原猜想条件完全一致，那么 58 和 60 之间这 2 个单位的缺口，就足以推翻该猜想。
4 条提示词，58 个英文单词
这次事件里，另一处受到关注的，是 Rybin 与 GPT-5.6 Pro 的公开对话方式。按披露信息，Rybin 在整个过程中没有使用大段提示词工程，也没有不断补充复杂公式。除附加文件外，他前后只给了模型 4 条提示词，总计 58 个英文单词。
第一轮任务发出后，GPT-5.6 Pro 先建立了一套线性规划验证方法，又尝试了超立方体、分层图、合并—分叉网络等多种结构，前后筛查了数千个小型实例。
但模型在第一轮搜索后并没有找到有效反例。它甚至提醒说，如果把现阶段的近似构造包装成反例，会得到错误的数学结论。
Rybin 没有补充新的公式，也没有直接给出路线，只是要求模型继续研究，找到一个完整、无条件的反例。第二轮搜索仍然失败。接着，他继续推动模型，让它基于对问题结构的理解，先形成明确策略，再往下寻找。
到第三轮时，GPT-5.6 Pro 已经把搜索范围缩小到一种只有 24 种状态的路由结构，但还是没有给出完整反例。直到第四条提示发出，要求用一个完整、无条件的反例收尾，模型才最终给出那张由 7 个节点、9 条有向边构成的小图。
模型中途多次走弯路
完整对话显示，GPT-5.6 Pro 在几个小时里并不是一路顺利。它曾多次找到看起来成立的候选反例，但在继续穷举所有路线后，又发现网络中存在此前漏掉的“混合路径”。
这些路径会从不同预设路线中各取一段，重新拼接成新的走法，从而绕开模型原先设计的容量限制。结果是，一些看似已经成立的反例，在完整验证后又被推翻。
GPT-5.6 Pro 对这一点的总结也很明确：只检查几百条预设路线远远不够，一个真正有效的反例，必须把网络中所有可能出现的不可分流路径全部计算进去。
58 个单词之外，人的作用是什么
表面上看，Rybin 贡献的只是 58 个英文单词。但从公开过程来看，他的关键动作在于判断模型前三轮给出的都只是阶段性结果，并且一次次拒绝提前结束搜索。
沃顿商学院教授 Ethan Mollick 看到这段过程后，提出了一个问题：这项工作的作者，到底应该算是写下 58 个单词的 Rybin，还是连续推演数小时的 GPT-5.6 Pro。
至少从这次公开对话里可以确认的是，GPT-5.6 Pro 最终交付的不只是一个口头上的“找到反例”，而是包括示意图、4 页证明证书、精确穷举验证程序、机器可读反例数据和 LaTeX 源码在内的一整套材料。
原文还提到，过去一周里，AI 在寻找数学反例上的推进，从雅可比猜想到 Dinitz-Garg-Goemans，速度已经明显加快。
本文来自微信公众号“量子位”，作者为梦瑶，MarsBit 发布了相关报道。