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 分享的聊天记录显示，模型最初是失败的，而且是如实失败。开场提示让它寻找一个结构化反例。它工作了将近一小时却空手而归，直言如果把已有内容当作有效反例呈现，那是错误的。

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

这不是“发四条提示就搞定”。而是一个模型花了数小时不断碰壁，并如实陈述问题所在。它反复撞上的那堵墙——额外路径出现并破坏分离——恰是最终构造试图避免的，通过把每个终端钉死在恰好两条路径上，使得整个路由空间仅有八种，可以手工枚举。记住这种失败模式。您马上就会自己撞上它。

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

自己检验

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

上代码前先来一句提醒：下面的内容不是 Rybin 的那张图。这是我为保证诚实而构建的示意实例：每个终端确实恰好有两条路径，算术闭合，差距真实。它展示了此类反例的形状以及检验技巧。它本身并不能推翻任何东西，我会在您运行之后解释原因。

设定如下：三个终端，各发运 10 单位，故最大需求 D 为 10。每个终端有一条昂贵直达路（成本 30）和一条免费便宜路。便宜路的安排是任意两条之间都会争夺一条各自私有的瓶颈路：1 与 2 共享道路 A，1 与 3 共享道路 B，2 与 3 共享道路 C。在分数流中，每个终端将 2/5 的需求走便宜路、3/5 走昂贵路，成本为 30 × 3/5 × 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 行枚举只有在每个终端真的只有两条路径且不多不少时才说真话。若用真实的道路与节点把这张图搭出来，组合结构往往会冒出第 4 条便宜路径。某个终端找到第三种便宜且不超预算的回家方式，差距就被抹平了。这个额外路径正是模型前三次尝试时报告的失败。用八行 Python 打造一个干净对称的小装置去击破一个 30 年的猜想，未免太完美——事实也确如此。上面的代码证明检验是可靠的、目标性质是明确的。而某张具体的图是否确实具备该性质、且没有任何“漏点”，才是难点所在——这也解释了为何 Rybin 的真实实例是参数族中的一个经过调参的点，而非一个整齐的三角形。

尚未解决的问题

目前尚无正式论文发表。Rybin 分享了对话与构造；二者都还没有经过可让数学界正式关闭该猜想的审稿流程。

我能找到的资料中，那张精确发布的图尚未被一手来源独立重建。坊间流传的数字来自他的帖子与共享的对话记录。数位研究者已核对其算术并称其一致，且有人指出该实例处在同一节点上的一个三参数无穷族中，这意味着该结果可能不只是一次偶然。令人鼓舞，但这只是社区层面的非正式检验，不是审稿报告。对 58 与 60 的差距，应将其当作“有力支撑的主张”，而非“定论”。

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

一种模式的一部分

这并非孤例。这是约三个月内据称第三个在 AI 协助下被击破的猜想，值得多停留片刻。

7 月 20 日，据报道 Claude Fable 5 帮助数学家 Levent Alpöge 找到了Jacobian 猜想的一个反例，这一问题已有 87 年历史。在此之前的 5 月，据称某个 OpenAI 模型已否定了有 80 年历史的 Erdős 单位距离猜想。与本条新闻同一周，一位哥伦比亚大学博士生使用 GPT-5.6 结合结构化 Codex 工作流，在五天内解决了六个 Erdős 未解问题。正如一位研究者所言，贯穿其间的主线是：这些系统更擅长“证伪”而非证明。反例是可核查的单个见证；证明则要覆盖所有情形。这样的不对称性似乎决定了哪些问题会先倒下。

现实层面的启示并不是“AI 解决数学”。我们所见的是 AI 作为耐心、可穷举的组合搜索伙伴在工作：它能枚举参数族、在多次尝试中记住失败模式，并在构造未闭合时如实相告。这是一种具体而有用的能力。若您想判断它下一次可能在哪发力，值得问的问题不是“哪个猜想更古老”，而是“哪些问题可以被一个可核查的单个见证击破”。