GPT-5.6 と Dinitz-Garg-Goemans 予想

2026年7月22日、Dmitry Rybin がXにある投稿を行い、一部の人々はコーヒーを置いた。GPT-5.6 Pro が、約30年にわたり組合せ最適化で未解決だった Dinitz-Garg-Goemans 予想の反例を生成したというのだ。概念実証は小さなグラフひとつ。分割可能フローのコストは58、分割不可能フローのコストは60。2ポイント、3十年、4つのプロンプト。

多くの報道は数字をなぞるばかりで、その背後の仕組みを示さない。しかし本当の教訓は仕組みにある。また、何が検証されていて何がそうでないのか、正直に説明すべき点もそこにある。短く言えば、概念は堅固で、ニュースは定理ではなく主張にすぎず、もし一からまったく同じグラフを再現しようと腰を据えて取り組むなら、再構成が水漏れを起こした瞬間に、なぜこの種の問題が難しいのかを身をもって理解することになる。

手短な答え

Rybin によれば、合計60語に満たない4つのプロンプトで誘導された GPT-5.6 Pro が、1999年頃から未解決の Goemans のコスト予想に対する反例を提示したという。彼の例は、単一の供給源と3つの配送端末を持つ小さな有向グラフである。分割可能（分数）ルーティングはコスト58で、許容された輻輳予算内に収める分割不可能ルーティングは最低でも60になると述べている。その2ポイントの差が、もし正式な査読に耐えれば、予想を沈めるのに十分だ。

この結果は査読を受けていない。Rybin は ChatGPT との対話全文を公開し、誰でも構成を読めるようにしている。複数人が彼の計算を確認し、一致していると報告した。ただし、再現可能な計算と受け入れられた証明はまったく別物であり、その距離こそがこの記事のすべてだ。

Dinitz-Garg-Goemans 予想とは？

何が崩れたのか、あるいは崩れたかもしれないのかを理解するには、まず予想が何を主張しているのかを知る必要がある。

倉庫が道路網を通じて3つの町に注文を配送する様子を思い浮かべてほしい。出荷を分割できるなら、注文の半分をある道に、残り半分を別の道に送れる。これが分数ルーティングで、柔軟性があるため、たいていはより安い経路集合を見つけられる。しかし実際の貨物の多くは分割できない。ひとつの注文はひとつのトラックで、ひとつの道路を最初から最後まで走る。これが分割不可能フローであり、実際に貨物、ネットワーク・パケット、コンテナが従う制約だ。

1999年から人々が噛み続けてきた問いは単純だ。もし安い分割可能ルーティングが存在するなら、道路に過負荷をかけすぎないようにしつつ、同じく安い分割不可能ルーティングを常に見つけられるのか？

Yefim Dinitz、Naveen Garg、Michel Goemans はそのうちの半分を解決した。もう半分こそ GPT-5.6 が狙った部分だ。その区別が非常に重要である理由を理解するには、正確に述べる必要がある。

定理と予想の違い

この違いは多くの解説で曖昧にされているので、ここで一度きちんと述べ、その後はこの記事全体でそれを前提にする。

Dinitz、Garg、Goemans は輻輳に関する結果を証明した。すなわち、有効な分数フローが与えられたとき、それを分割不可能フローに変換しても、どの道路の容量も最大需要（その値を D とする）分を超えて上振れしない、というものだ。この定理は問題視されておらず、これまでもそうだった。

一方で Goemans が別に予想したのは、より強いコスト考慮の版である。すなわち、同じ変換で輻輳を抑えると同時に、合計コストも抑えられるというもの。ひとつのルーティングで、輻輳とコストの双方が有界に保たれる。輻輳のみの定理は安全だ。コスト＋輻輳の予想こそ、Rybin が崩れたと言っている部分である。この記事から一文だけ持ち帰るなら、それにしてほしい。多くの興奮した報道は両者をこっそり入れ替えており、その違いこそ、解くのに30年かかった数学的な隔たりのすべてだ。

GPT-5.6 が実際に作ったもの

Rybin のインスタンスは、ひとつの段落で説明できるほど小さい。供給源、共有の「背骨」を形づくる中間ノード群、そして需要を持つ3つの端末。各端末には2つの帰り道がある。高価な直行パスか、共有の背骨を通る無料の迂回路か。

緊張は構造的だ。安い迂回路は背骨の容量を奪い合うため、あまりに多くの端末が同時に安く通ろうとすると、背骨の道路があふれてしまう。そこまで押しやると、有効な分割不可能ルーティングでは安い道を取れる端末はせいぜいひとつになり、残りは高価な直行パスに追いやられ、コストが跳ね上がる。分数フローは分割できるので、それぞれの需要を両方の道に分散し、すべての容量制約を同時にすり抜ける。これが、最も安い合法的な分割不可能コストを、分数コストが下回る仕組みだ。Rybin の例の数字は 58 と 60 である。

ここで限界を正直に述べておく。私は一次情報から、Rybin の正確なグラフ、具体的な容量や二項対立関係を再現することができていない。彼の書き起こしはパラメータ族の特定の点を記述しており、広く共有されている「7ノード」という説明は、その抽象であって、私が枝ごとに検証した構成ではない。だから私は、58 をきれいに導出して彼のもののように装うつもりはない。私にできるのは、同じ仕組みを示す自足的なインスタンスを手渡すことだ。総当たりで確かめられる程度に小さく、「分数があらゆる合法的な分割不可能を上回る」とはどういうことかを自分の目で見られるようにすることである。

4つのプロンプト、数時間

この話でもっとも興味がないのはプロンプトの回数だが、それが拡散された部分でもある。

Rybin が共有したチャットログでは、モデルは最初に失敗し、しかも正確に失敗している。最初のプロンプトは、構造化された反例の発見を求めた。モデルはほぼ1時間にわたり作業し、成果はなしとして戻ってきた。手元のものを有効な反例として提示するのは誤りだと明言して。

続行を指示すると、再び走らせ、再び何もなしと報告した。有望に見えた構成のすべてが、最終的に全経路を列挙すると隠れた追加経路を生み、それがコストと輻輳の分離を壊してしまうと説明した。さらに、より洗練された戦略を求める三度目のプロンプトでは、より狭い枠組みを得たものの、やはり完成には至らなかった。

これは「4プロンプトで完了」ではない。何時間もモデルが壁にぶつかり、その事実を正直に伝えているのだ。たびたび突き当たった特定の壁——余計な経路が現れて分離を台無しにする——こそ、最終構成で防ごうとした事象であり、各端末をちょうど2本の経路にピン留めして、ルーティング空間全体を手作業で列挙できる8通りにした。あの失敗モードは覚えておいてほしい。これからあなた自身がそれに直面することになる。

4つ目のプロンプトは、おおむね 「失敗はもう十分。無条件の完全な反例で締めくくってください」といった内容で、これが動作する構成を生み、証明書、列挙プログラム、完全な LaTeX とともに提示された。辛抱が効いた。そして、それ以前の拒否も同様に重要だった。正直な自己評価だったのだ。

自分で確かめよう

ここからが、ニュース記事にはできない DataCamp の出番だ。検証を自分で実行できる。

コードの前にひとつ注意。これから示すのは Rybin のグラフではありません。正直さを重視して私が作った概略的なインスタンスで、各端末が本当にちょうど2本の経路しか持たず、計算が閉じ、ギャップが実在するものだ。反例の形と、その検証手法を示す。これ単体では何も反証しない。その理由は、実行後に説明する。

設定：3つの端末がそれぞれ10ユニットを出荷し、最大需要 D は10。各端末には高価な直行パス（コスト30）と無料の安いパスがある。安いパスは、任意のペアがそれぞれ固有のボトルネック道路を取り合うように配置されている。道路Aは端末1と2が共有、道路Bは1と3、道路Cは2と3。分数フローでは、各端末は需要の2/5を安いパス、3/5を高価なパスに流すので、コストは 30 × 3/5 × 3 = 54。各道路は分数的に 4 + 4 = 8 ユニットを運び、輻輳予算はその負荷に D を足した 18 になる。

ここで分割不可能ルーティングがどうなるかを見る。2つの端末がともに安いパスを選ぶと、共有道路に 10 + 10 = 20 ユニットが流れ、予算の18を超える。ゆえに安いパスを取れる端末は最大1つで、残り2つはそれぞれ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になる。過負荷となる3行は3つのペアの競合であり、通過できるルーティングは、安いパスを取る端末が高々ひとつのものだけだ。

では予想は死んだのか？ そう単純ではない。ここが約束した説明箇所だ。あの8行の列挙が真実を語るのは、各端末が現実に2本の経路しか持たない場合に限られる。このグラフを実際の道路とノードで構成すると、組合せから第4の安い経路が現れがちだ。端末が第3の安い帰路を見つけ、それが予算内に収まり、ギャップが消える。この余計な経路こそ、モデルが最初の3回で報告した失敗の正体だ。8行の Python で30年もの予想を壊す、きれいで対称なガジェット——それが本当なら良すぎる話で、実際に良すぎる。上のコードが証明するのは、検査が健全で、目標となる性質が実在することだ。あるグラフが本当にその性質を「漏れなく」持つかどうかが難所であり、Rybin の実例が、きれいな三角形ではなく、パラメータ族の中の調整された一点になっている理由でもある。

未解決の点

正式な論文はまだ出ていない。Rybin は対話と構成を共有したが、予想を公式に閉じるための査読プロセスは通っていない。

公開された正確なグラフは、私が見つけた限り、一次情報から独立に再構築されていない。出回っている数字は彼の投稿と共有された書き起こしに基づく。複数の研究者が計算を確認し一貫していると述べ、ひとりは、同じノード上の無限の3パラメータ族の内部にそのインスタンスが位置していることを示した。もしそうなら、単なる幸運の一発ではなく、より豊かな結果になる。心強いが、これはコミュニティの非公式なチェックであり、査読報告ではない。58対60は裏付けの厚い主張として扱い、既成事実とは見なさないでほしい。

1999年の輻輳定理は、この件のいかなる影響も受けていない。

ひとつのパターンの一部

この話は孤立した事例ではない。ここ3か月ほどで、AIの助けで崩れたと報告された予想はこれで3つ目だ。このパターンは注目に値する。

7月20日には、Claude Fable 5 が数学者 Levent Alpöge のヤコビアン予想の反例発見を助けたと報じられた。これは87年物の問題だ。その前の5月には、OpenAI のモデルが80年物の Erdős の単位距離予想を反証したとされた。同じ週、コロンビア大の博士課程の学生が、構造化された Codex ワークフローと GPT-5.6 を用いて、5日で6つの未解決の Erdős 問題を解いた。ある研究者が述べたとおり、これらのシステムは反証のほうが証明より得意だという通底がある。反例は単一の証人を検査すればよいが、証明はすべてのケースを覆わねばならない。この非対称性が、どの問題が先に倒れるかを決めているようだ。

実務的な教訓は「AIが数学を解く」ではない。我々が目にしているのは、AIが辛抱強く、組合せ的に網羅的な探索パートナーとして機能している姿だ。パラメータ族を列挙し、失敗モードを試行間で作業記憶に保持し、構成が閉じないときには真実を伝えられる。これは特定かつ有用な能力である。そして次にどこに現れそうかを知りたいなら、問うべきは「どの予想が古いか」ではなく、「単一の検査可能な証人で破れる予想はどれか」である。