GPT-5.6 与 Dinitz-Garg-Goemans 猜想

2026 年 7 月 22 日，Dmitry Rybin 在 X 上发布了一条让某类人放下咖啡的消息：GPT-5.6 Pro 给出了 Dinitz-Garg-Goemans 猜想的一个反例，这一组合优化难题已悬而未决约 30 年。其概念验证是一个小图。可分流成本为 58，不可分流成本为 60。两个数字，三十年，四条提示。

多数报道只复述了数字，却没展示其背后的机制，而机制才是关键之处。也是我必须如实说明哪些已被验证、哪些尚未的地方。简而言之：概念稳固，消息仍是主张而非定理；当您坐下来从零重建那张精确的图时，会在复现过程第一次“漏水”的瞬间明白为什么这类问题如此棘手。

快速结论

据 Rybin 报告，GPT-5.6 Pro 在四条、总字数不到 60 的提示引导下，给出了 Goemans 成本猜想的一个反例，该问题自约 1999 年以来一直开放。他给出的实例是一张小型有向图，包含一个源点和三个投递终端。他称，可分（分数）路由的成本为 58，而任何在拥塞不超预算的前提下的不可分路由成本至少为 60。若这 2 点差距经得起正式审查，便足以推翻该猜想。

该结果尚未经同行评审。Rybin 发布了完整的 ChatGPT 对话，任何人都可阅读其构造；已有多人核对其算术并认为一致。但可复现的算术与被接受的证明并非同一回事，而两者之间的距离正是本文的全部话题。

什么是 Dinitz-Garg-Goemans 猜想？

要理解倒下的到底是什么，或可能是什么，得先弄清猜想本身在说什么。

想象一个仓库经由公路网向三个城镇发货。如果允许拆分货物，您可以把一份订单的一半走这条路，另一半走那条路。这就是分数路由，灵活，通常能找到更便宜的路径集合。但许多真实货运无法拆分：一单、一车、一条路，从头到尾。这就是不可分流，也是货运订单、网络包或集装箱在现实中必须遵循的方式。

自 1999 年以来，人们一直在思考的一个问题表述很简单：若存在一种便宜的可分路由，是否总能找到一种不可分路由，也能便宜，同时不至于把道路过载得太厉害？

Yefim Dinitz、Naveen Garg 和 Michel Goemans 解决了一半。另一半正是 GPT-5.6 试图攻克的部分。要理解为何这一差别至关重要，我们得精确表述它。

定理 vs. 猜想

这是多数报道模糊处理的区别，我在这里精准说明一次，后文将依此展开。

Dinitz、Garg 和 Goemans 证明了一个关于拥塞的结果：给定一个有效的分数流，总可以把它转换为一个不可分流，使任一道路的容量超载不超过最大单一需求，记为 D。该定理没有争议，从未有过。

而 Goemans 另行猜想的是更强的、考虑成本的版本：同样的转换能否在控制拥塞的同时把总成本也压住？拥塞与成本双双有界，合于一体的路由。仅拥塞的定理是稳固的；拥塞加成本的猜想则是 Rybin 声称被推翻的那一块。若只记住本文的一句话，请记住这句。很多兴奋的报道悄然将两者混为一谈，而它们的差别正是这道横跨 30 年的数学鸿沟。

GPT-5.6 实际构建了什么

Rybin 的实例小到可以用一段话描述：一个源点、几个形成共享“主干”的中间节点，以及三个各自承载需求的终端。每个终端有两条回家的路：一条昂贵的直达路径，或经由共享主干的免费绕行。

其中的张力是结构性的。便宜的绕行会争抢主干上的空间，因此若同时尝试走便宜路的终端太多，某条主干道路就会溢出。若推进到这种程度，在任何有效的不可分路由中，至多只有一个终端能走便宜路。其余被迫走昂贵直达，成本上升。分数流则可自由拆分，把每个需求分摊到两条路上，同时低于每条容量。这就是为什么分数成本能低于最便宜的合法不可分成本。Rybin 的数字是 58 与 60。

我必须坦诚一个限制：我没能从一手资料复现 Rybin 的那张精确图，即具体的容量与两两冲突关系。他的对话稿描述的是某个参数族中的一个特定点，而流传甚广的“七节点”描述是对其的抽象，不是我逐边验证过的构造。所以我不会摆出一套整洁的 58 推导并假装那是他的。我要做的，是给您一个自洽的实例，展示同样的机制，小到可以用暴力法检查，让您亲眼看看“分数路由击败所有合法不可分路由”是什么样子。

四条提示，数小时的过程

提示条数是这个故事里最不有趣的部分，尽管它成了病毒传播的焦点。

Rybin 分享的聊天记录显示，模型最初失败了，而且是如实地失败。开场提示要求找一个结构化的反例。它工作了近一小时却空手而归，直言若把已有内容当作有效反例呈现会是错误的。

继续要求其尝试后，它又运行了一次，再次报告无果，并描述每个看似有希望的构造在枚举完所有路径后总会冒出一个隐藏的额外路由选项，摧毁了成本与拥塞的分离。第三条提示要求更干净的策略，换来了更窄的框架，仍未得到最终结果。

这不是“四条提示就搞定”。而是一个模型连续数小时碰壁，并如实告知问题所在。它反复撞到的那面具体“墙”——额外路线出现并破坏分离——恰是最终构造通过把每个终端钉死在恰好两条路径上所要避免的，这样整个路由空间只有 8 种可能，您可以手工枚举。记住这种失败模式，您马上也会遇见它。

第四条提示，据称近似于“受够了你的失败，请给出完整、无条件的反例”，就是产出可用构造的一次，同时附带证明证书、枚举程序和完整 LaTeX。耐心很重要。先前的拒绝同样重要；它们是诚实的自我评估。

自己动手检验

这正是 DataCamp 的报道能做而新闻帖做不到的：让您亲自运行验证。

在上代码前先提示一下：下面的内容不是 Rybin 的图。这是我为求诚实而搭的示意实例，在其中每个终端都被真实地限定为恰好两条路线，算术闭合，且差距确实存在。它展示了此类反例的形状及其检查方法。本身并不能推翻任何结论，原因我会在您跑完后解释。

设定如下：三个终端，各运 10 单位，故最大需求 D 为 10。每个都有一条昂贵的直达路（成本 30）和一条免费的便宜路。便宜路的安排使得每一对终端都为一条各自专属的瓶颈路所争抢：道路 A 由终端 1 与 2 共享，道路 B 由 1 与 3 共享，道路 C 由 2 与 3 共享。在分数流里，每个终端把其 2/5 的需求走便宜路、3/5 走昂贵路，总成本为 30 x 3/5 x 3 = 54。于是每条道路分数载荷为 4 + 4 = 8，拥塞预算为该载荷加 D，即 18。

看看不可分路由会发生什么。两个终端同时走便宜路，会在其共享道路上倾倒 10 + 10 = 20 单位，超过 18 的预算。因此至多只能有一个终端走便宜路；另两个各付 30。不可分路由的最低合法成本：60。对比分数成本 54。共有 8 种路由，逐一检查即可：

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# The fractional flow saturates each road, so its load is that road's capacity
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # this terminal takes its cheap path
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "overload"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

运行后，您会得到分数成本 54、最低合法不可分成本 60、差距为 6。三行“超载”的情形对应三对两两冲突；仅保留至多一个终端走便宜路的路由才是合法的。

那么猜想就此作古？并不，这正是我承诺要解释的部分。那 8 行枚举只有在每个终端确实只有两条路线、没有更多时才完全成立。把这张图用真实的道路与节点搭起来后，往往会从组合结构中冒出第四条便宜路线。某个终端会找到第三条既便宜又不超预算的回家路，差距随之消失。这个额外路线正是模型前三次尝试中报告的失败所在。一个干净、对称的小工具若能用 8 行 Python 打破一个 30 年的猜想，那将好到不真实，而事实确实如此。上面的代码证明了检验方法是可靠的，目标性质是真实存在的。某张具体的图是否具备该性质、且没有“漏点”，才是困难所在，这也是为何 Rybin 的真实实例是参数族中的一个调谐点，而不是一个整洁的三角形。

尚未解决的部分

目前尚无正式论文发表。Rybin 分享了对话与构造；二者都未经过审稿流程，数学界也尚未据此正式关闭该猜想。

我能找到的资料中，并没有从一手来源独立重建那张已发布的图。流传的数字来自他的帖子与共享的对话稿。已有多位研究者核对其算术并称之为一致，且有人展示他的实例位于同一节点集上的一个无限三参数族中，这会让结果比一次“幸运巧合”更有分量。令人鼓舞，但这仍是社区的非正式核查，而非审稿报告。请将 58 对 60 视作有力支持的主张，而非尘埃落定的事实。

1999 年的拥塞定理不受上述任何影响。

一种模式的一部分

这不是单一的个案。大约三个月内，已有第三个猜想被报道在 AI 协助下告破，这一模式值得玩味。

7 月 20 日，据称 Claude Fable 5 帮助数学家 Levent Alpöge 找到一个雅可比猜想的反例，这是一个有 87 年历史的问题。在此之前的 5 月，据称某个 OpenAI 模型否定了有 80 年历史的 Erdős 单位距离猜想。就在本新闻同期，哥伦比亚大学的一位博士生使用 GPT-5.6 与结构化 Codex 工作流，在 5 天内解决了 6 个开放的 Erdős 问题。正如一位研究者所言，贯穿其中的主线是，这些系统更擅长推翻而非证明。反例是一个可以检查的单一见证；证明必须覆盖所有情形。这种不对称似乎决定了哪些问题会先倒下。

现实启示并非“AI 解出数学”。我们所见的是，AI 作为一位耐心、在组合层面上穷尽搜索的伙伴在工作：它能枚举参数族、在多次尝试间把失败模式保留在工作记忆中，并在构造未闭合时说出真相。这是一种具体且有用的能力。若您想判断它下一步可能在哪发力，应该问的问题不是哪些猜想最古老，而是哪些问题可以被一个可检验的单一见证所击破。