GPT-5.6 と Dinitz–Garg–Goemans 予想

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

多くの報道は数字を繰り返すだけで、その背後の仕組みを示していません。本当の教訓はその仕組みにあります。そしてそこでは、何が検証され、何がまだなのかを正直にお伝えする必要があります。短いまとめ：概念は堅固で、ニュースは定理ではなく主張にすぎません。ゼロからまったく同じグラフを再現しようと腰を据えると、再構成にほころびが出た瞬間に、なぜこの種の問題が難しいのかがわかります。

手早い答え

Rybin の報告によれば、60 語未満の 4 つのプロンプトで誘導された GPT-5.6 Pro が、1999 年ごろから未解決だった Goemans のコスト予想に対する反例を提示しました。彼の例は、単一の送信元と 3 つの配送端末を持つ小さな有向グラフです。分割可能（分数）ルーティングのコストは 58、一方で混雑を許容範囲に収める任意の分割不能ルーティングのコストは少なくとも 60 だと述べています。もしその 2 ポイントの差が正式な査読を生き残れば、この予想は覆ります。

まだ査読は受けていません。Rybin は ChatGPT とのやり取り全体を公開し、誰でも構成を読めるようにしました。複数の人が計算を確認し、一貫していると指摘しています。とはいえ、再現可能な算術と、受理された証明は別物であり、その隔たりこそが本稿のすべてです。

Dinitz–Garg–Goemans 予想とは何か？

何が崩れたのか、あるいは崩れたかもしれないのかを理解する前に、予想が実際に何を主張しているのかを把握する必要があります。

道路網を通じて倉庫が 3 つの町へ出荷する場面を思い浮かべてください。出荷を分割できるなら、注文の半分をこちらの道、もう半分を別の道に送れます。これが分数ルーティングで、柔軟です。たいていはより安い経路集合を見つけられます。しかし実際の貨物の多くは分割できません。1 注文、1 台のトラック、1 本の道路、最初から最後まで。これが分割不能フローで、現実の貨物、ネットワークパケット、コンテナが実際に従う制約です。

1999 年以来議論されてきた問いは、表現は簡単です。安い分割可能ルーティングが存在するなら、道路の過負荷をひどく起こさずに、同様に安い分割不能ルーティングを常に見つけられるのか？というものです。

Yefim Dinitz、Naveen Garg、Michel Goemans はそのうち半分を解決しました。GPT-5.6 が挑んだのはもう半分の方です。その違いがなぜ非常に重要なのかを理解するには、ここで厳密さが必要です。

定理と予想の違い

多くの記事がここを曖昧にします。そこで一度だけ正確に述べ、以降はその区別に依拠します。

Dinitz、Garg、Goemans は混雑に関する結果を証明しました。すなわち、妥当な分数フローが与えられたとき、それを分割不能フローへ変換しても、どの道路の容量も最大需要 D（最大の要求量）を上回る分以上には超過しない、というものです。この定理は議論の余地がなく、これまでも問題視されていません。

一方で Goemans が別途予想したのは、より強いコストを考慮した版です。すなわち同じ変換で、混雑を抑えつつ同時に総コストも抑えられるというもの。混雑とコストの双方が、一つのルーティングで有界であるという主張です。混雑のみの定理は安全です。コストと混雑の両立をうたう予想こそが、Rybin が崩れたと言っている部分です。本稿から 1 文だけ持ち帰るなら、これにしてください。多くの興奮気味の記事は、こっそり両者を入れ替えています。しかしその違いこそ、30 年をかけて埋められた数学的な溝のすべてなのです。

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

Rybin のインスタンスは、1 段落で説明できるほど小さいものです。送信元、共通の「背骨」を形成する中間ノード群、そして需要を持つ 3 つの端末。各端末には 2 つの帰路があり、コストの高い直通経路か、共通の背骨を通る無料の迂回路かのいずれかです。

緊張は構造的です。安い迂回路は背骨上の容量を奪い合います。そのため、端末が同時に安い経路を取りすぎると、背骨の道路があふれます。そこまで押しやると、どの妥当な分割不能ルーティングでも安い経路を取れるのはせいぜい 1 つの端末だけになります。残りは高価な直通経路に追いやられ、コストが上がります。一方、分数フローは自由に分割できるので、各需要を両方の経路に分散させ、同時にすべての容量制約の下をすり抜けます。これが、最も安い合法的な分割不能コストを下回る分数コストが生じる仕組みです。Rybin の例では数値は 58 と 60 です。

ここで限界を正直に述べます。一次情報から、Rybin の正確なグラフ――具体的な容量やペアごとの競合――を再現することはできていません。彼の書き起こしはパラメータ族のある一点を記述しており、広く共有されている「7 ノード」の説明はその抽象化であって、私が辺ごとに検証した構成ではありません。ですから、きれいな 58 の導出を並べて、彼のものだと装うつもりはありません。私にできるのは、同じ仕組みを示す自己完結のインスタンスをお渡しすることです。総当たりでチェックできる程度に小さく、分数が「すべての合法的な分割不能を上回る」とは何かを自分の目で確かめられるものを。

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

バズったのはプロンプトの少なさですが、物語としてはそこが一番つまらない部分です。

Rybin が共有したチャットログでは、モデルは最初に失敗しています――しかも正確に失敗しています。冒頭のプロンプトは、構造化された反例を求めるものでした。モデルは 1 時間近く作業したものの空振りで戻り、手元のものを妥当な反例として提示するのは虚偽だとはっきり述べました。

続行を指示され、再度走らせてもまた収穫なし。見込みのある構成を挙げながら、すべての経路を列挙すると隠れた追加経路が見つかり、それがコストと混雑の分離を壊してしまう、と説明しました。3 回目は、よりすっきりした戦略を求めるプロンプトで枠組みは絞れたものの、完成品はまだ出ませんでした。

つまり「4 プロンプトで完了」ではありません。モデルが何度も壁に当たり、その事実を正直に伝えた数時間なのです。繰り返しぶつかった具体的な壁――余計な経路が現れて分離を台無しにする――こそ、最終構成が防ぐよう設計されていたものです。各端末をちょうど 2 本の経路に固定し、ルーティング空間全体を 8 通りにして手で列挙できるようにしました。この失敗モードは覚えておいてください。これからご自身でも直面します。

4 本目のプロンプトは、「失敗はもう十分。無条件の完全な反例で仕上げてください」に近い文言だったとされ、これが動く構成を生みました。証明証明書、列挙プログラム、完全な LaTeX 付きです。忍耐が奏功しました。同様に、先の拒否も重要でした。正直な自己評価だったからです。

自分で確かめてください

ここからは、DataCamp の記事だからこそできること――検証を実行できます。

コードの前に短い注意点。これから示すのはRybin のグラフではありません。各端末が本当に厳密に 2 つの経路しか持たず、算術が閉じ、差が実在するよう、誠実さを重視して私が作った模式的なインスタンスです。こうした反例の形と、その検査手法を示すものです。これ単体では何も反証しません。その理由は、実行後に説明します。

設定：3 つの端末が各 10 単位を出荷するので、最大需要 D は 10。各端末には高価な直通経路（コスト 30）と無料の安価経路が 1 つずつあります。安価経路は、各ペアが固有のボトルネック道路を取り合うよう配置されています。道路 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 組のペアごとの競合に対応しています。生き残るルーティングは、安価経路を取る端末が最大 1 つに留まるものだけです。

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

未解決の点

正式な論文はまだ出ていません。Rybin は会話と構成を共有しましたが、予想を公式に閉じるために必要な査読は通っていません。

公開された正確なグラフは、私の知る限り一次情報から独立に再構築されていません。出回っている数値は、彼の投稿と共有された書き起こしに由来します。複数の研究者が計算を確認して矛盾なしと述べ、また 1 人は彼のインスタンスが同じノード上の 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 が辛抱強く組合せ的に網羅探索を行うパートナーとして機能している姿です。パラメータ族を列挙し、失敗モードを試行間で作業記憶に保持し、構成が閉じないときに真実を伝えられる存在。その能力は具体的で有用です。そして次にどこを突く可能性が高いのかを理解したいなら、問うべきは「どの予想が古いか」ではなく、「単一の検証可能な目撃情報で壊せるものはどれか」です。