GPT-5.6 und die Dinitz-Garg-Goemans-Vermutung

Am 22. Juli 2026 postete Dmitry Rybin auf X eine Behauptung, bei der manche Leute den Kaffee abstellten: GPT-5.6 Pro habe ein Gegenbeispiel zur Dinitz-Garg-Goemans-Vermutung konstruiert, einem offenen Problem der kombinatorischen Optimierung seit rund 30 Jahren. Der Beweisansatz war ein kleiner Graph. Fraktionierte Flusskosten 58, unteilbare Flusskosten 60. Zwei Punkte, drei Jahrzehnte, vier Prompts.

Die meisten Berichte wiederholen die Zahlen, ohne den dahinterliegenden Mechanismus zu zeigen, und genau darin liegt die eigentliche Lektion. Hier muss ich auch klar sagen, was verifiziert ist und was nicht. Kurzfassung: Die Konzepte sind solide, die Meldung ist eine Behauptung und noch kein Theorem, und wenn du dich hinsetzt, um den exakten Graphen von Grund auf nachzubauen, merkst du sofort, warum solche Probleme hart sind, sobald deine Rekonstruktion irgendwo undicht wird.

Die schnelle Antwort

Rybin berichtet, dass GPT-5.6 Pro, gelenkt von vier Prompts mit insgesamt unter 60 Wörtern, ein behauptetes Gegenbeispiel zu Goemans’ Kostenvermutung geliefert hat, einem seit etwa 1999 offenen Problem. Sein Beispiel ist ein kleiner gerichteter Graph mit einer Quelle und drei Zielknoten. Er gibt an, dass die teilbare (fraktionierte) Routenführung 58 kostet, während jede unteilbare Routenführung, die die zulässige Überlastung einhält, mindestens 60 kostet. Diese Zweipunktlücke reicht, wenn sie die formale Prüfung übersteht, um die Vermutung zu kippen.

Es gab noch kein Peer-Review. Rybin hat das vollständige ChatGPT-Gespräch veröffentlicht, sodass jede Person die Konstruktion nachlesen kann, und mehrere haben seine Rechnungen geprüft und als konsistent befunden. Reproduzierbare Arithmetik und ein anerkannter Beweis sind jedoch zwei verschiedene Dinge, und die Distanz dazwischen ist die ganze Geschichte dieses Artikels.

Was ist die Dinitz-Garg-Goemans-Vermutung?

Bevor wir wertschätzen können, was gefallen ist – oder gefallen sein könnte –, müssen wir verstehen, was die Vermutung tatsächlich aussagt.

Stell dir ein Lager vor, das Bestellungen über ein Straßennetz in drei Städte verschickt. Wenn du eine Lieferung aufteilen darfst, kannst du eine Hälfte über die eine Straße und die andere Hälfte über eine andere schicken. Das ist fraktionierte Routenführung, sie ist flexibel und findet meist günstigere Wege. Viel reale Fracht lässt sich aber nicht teilen. Eine Bestellung, ein Lkw, eine Straße, vom Start bis zum Ziel. Das ist unteilbarer Fluss – so verhalten sich Frachtaufträge, Netzpakete oder Container in der Praxis.

Die Frage, an der seit 1999 geknabbert wird, ist einfach formuliert. Wenn es eine günstige teilbare Routenführung gibt, findest du dann immer auch eine unteilbare, die ebenfalls günstig ist, ohne die Straßen zu stark zu überlasten?

Yefim Dinitz, Naveen Garg und Michel Goemans haben die eine Hälfte davon bewiesen. Die andere Hälfte ist die, auf die GPT-5.6 zielte. Um zu verstehen, warum diese Unterscheidung enorm wichtig ist, müssen wir präzise werden.

Der Satz vs. die Vermutung

Diese Unterscheidung wird in vielen Artikeln verwischt, daher bin ich hier einmal genau und beziehe mich im Rest des Textes darauf.

Dinitz, Garg und Goemans haben einen Überlastungs-Satz bewiesen: Gegeben einen gültigen fraktionierten Fluss, kannst du ihn immer in einen unteilbaren umwandeln, ohne die Kapazität irgendeiner Straße um mehr als die größte Einzelnachfrage – nennen wir sie D – zu überschreiten. Dieser Satz steht nicht zur Debatte und stand es nie.

Was Goemans separat vermutete, ist die stärkere, kostenbewusste Version: dass dieselbe Umwandlung gleichzeitig die Gesamtkosten niedrig halten kann, während sie die Überlastung begrenzt. Überlastung und Kosten, beide beschränkt, in einer Routenführung. Der Überlastungs-Satz allein ist sicher. Die Kosten-plus-Überlastungs-Vermutung ist das Teil, das laut Rybin gefallen ist. Wenn du nur einen Satz aus diesem Text mitnimmst, dann diesen. Viele der euphorischen Berichte tauschen beides stillschweigend aus, und der Unterschied zwischen ihnen ist genau die mathematische Lücke, deren Schließung 30 Jahre gedauert hat.

Was GPT-5.6 tatsächlich gebaut hat

Rybins Beispiel ist klein genug für eine Beschreibung in einem Absatz. Eine Quelle, einige Zwischenknoten, die eine gemeinsame „Wirbelsäule“ bilden, und drei Ziele, jedes mit einer Nachfrage. Jedes Ziel hat zwei Wege nach Hause: einen teuren direkten Pfad oder einen kostenlosen Umweg über die gemeinsame Wirbelsäule.

Die Spannung ist strukturell. Die günstigen Umwege konkurrieren um Platz auf der Wirbelsäule. Wenn zu viele Ziele gleichzeitig billig routen, läuft eine Wirbelsäulenstraße über. Treibt man das weit genug, kann in jeder gültigen unteilbaren Routenführung nur ein Ziel seinen günstigen Weg nehmen. Die übrigen werden auf ihre teuren direkten Pfade gezwungen, und die Kosten steigen. Der fraktionierte Fluss, frei zu teilen, verteilt jede Nachfrage auf beide Wege und bleibt gleichzeitig unter allen Kapazitäten. So erhältst du fraktionierte Kosten unterhalb der günstigsten zulässigen unteilbaren Kosten. Rybins Zahlen für sein Beispiel sind 58 und 60.

Ich bin ehrlich zu einer Grenze hier. Ich konnte Rybins exakten Graphen, die spezifischen Kapazitäten und Paar-Konflikte, nicht aus einer Primärquelle rekonstruieren. Sein Transkript beschreibt einen bestimmten Punkt in einer Parameterfamilie, und die viel geteilte „Sieben-Knoten“-Skizze ist eine Abstraktion davon, keine Konstruktion, die ich Kante für Kante verifiziert habe. Daher werde ich keine saubere Herleitung der 58 inszenieren und so tun, als sei es seine. Was ich kann, ist dir ein in sich geschlossenes Beispiel zu geben, das denselben Mechanismus zeigt – klein genug, um es per Bruteforce zu prüfen –, damit du mit eigenen Augen siehst, wie „fraktioniert schlägt jede zulässige unteilbare“ aussieht. 

Vier Prompts, mehrere Stunden

Die Zahl der Prompts ist das am wenigsten interessante an dieser Geschichte, auch wenn genau das viral ging.

Das von Rybin geteilte Chatprotokoll zeigt, dass das Modell zuerst scheiterte – und zwar akkurat scheiterte. Der erste Prompt bat um ein strukturiertes Gegenbeispiel. Es arbeitete fast eine Stunde und kam ohne Ergebnis zurück, ausdrücklich mit dem Hinweis, dass es falsch wäre, das Gefundene als gültiges Gegenbeispiel zu präsentieren.

Aufgefordert, weiterzumachen, lief es erneut und meldete wieder nichts – mit der Beschreibung, wie jede vielversprechende Konstruktion bei vollständiger Aufzählung der Pfade eine versteckte zusätzliche Routenoption enthüllte, die die Trennung von Kosten und Überlastung zerstörte. Ein dritter Prompt mit der Bitte um eine sauberere Strategie brachte einen engeren Rahmen, aber noch kein fertiges Ergebnis.

Das ist nicht „vier Prompts, fertig“. Das sind Stunden, in denen ein Modell gegen Wände läuft und die Wahrheit darüber sagt. Die konkrete Wand, gegen die es immer wieder lief – eine zusätzliche Route taucht auf und ruiniert die Trennung –, ist genau das, was die finale Konstruktion verhindert, indem sie jedes Ziel exakt auf zwei Pfade festnagelt, sodass der gesamte Routingspace aus acht Optionen besteht, die du per Hand aufzählen kannst. Behalte diesen Fehlermodus im Kopf. Du wirst gleich selbst darüber stolpern.

Der vierte Prompt, dem Vernehmen nach etwas wie „jetzt reicht’s mit deinem Scheitern, bitte liefere ein vollständiges, bedingungsloses Gegenbeispiel“, lieferte dann die funktionierende Konstruktion – inklusive Zertifikaten, einem Enumerationsprogramm und vollständigem LaTeX. Die Geduld war entscheidend. Ebenso die vorherigen Verweigerungen; sie waren ehrliche Selbsteinschätzungen.

Prüf es selbst

Hier kann DataCamp etwas leisten, was ein News-Post nicht kann: dich die Verifikation laufen lassen.

Ein kurzer Hinweis vor dem Code. Was folgt, ist nicht Rybins Graph. Es ist ein schematisches Beispiel, das ich so gebaut habe, dass es ehrlich ist: Jedes Ziel hat genau zwei Routen, die Rechnung geht auf, und die Lücke ist real. Es zeigt dir die Form eines solchen Gegenbeispiels und die Technik zur Prüfung. Für sich genommen widerlegt es nichts, und gleich danach erkläre ich, warum.

Das Setup: drei Ziele mit je 10 Einheiten Nachfrage, also ist die größte Nachfrage D gleich 10. Jedes hat einen teuren Direktpfad (Kosten 30) und einen kostenlosen günstigen Pfad. Die günstigen Pfade sind so angeordnet, dass jedes Paar über seine eigene Engpassstraße konkurriert: Straße A wird von Ziel 1 und 2 geteilt, Straße B von Ziel 1 und 3, Straße C von Ziel 2 und 3. Im fraktionierten Fluss schickt jedes Ziel 2/5 seiner Nachfrage günstig und 3/5 teuer, was 30 × 3/5 × 3 = 54 kostet. Jede Straße trägt dann fraktioniert 4 + 4 = 8 Einheiten, und das Überlastungsbudget ist diese Last plus D, also 18.

Jetzt sieh dir an, was unteilbare Routenführung daraus macht. Wenn zwei Ziele beide günstig gehen, landen 10 + 10 = 20 Einheiten auf ihrer gemeinsamen Straße – über dem Budget von 18. Also kann höchstens ein Ziel günstig routen; die anderen beiden zahlen je 30. Minimale zulässige unteilbare Kosten: 60. Gegenüber fraktionierten 54. Es gibt acht Routenwahlen, also prüfen wir einfach alle:

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)")

Du erhältst fraktionierte Kosten von 54, minimale zulässige unteilbare Kosten von 60 und eine Lücke von 6. Die drei überladenen Zeilen sind die drei paarweisen Konflikte; gültig bleiben nur die Routenwahlen, die höchstens ein Ziel günstig lassen.

Also ist die Vermutung tot? Noch nicht, und das ist der Teil, den ich versprochen habe zu erklären. Diese Acht-Zeilen-Aufzählung sagt nur dann die Wahrheit, wenn jedes Ziel wirklich genau zwei Routen und keine weitere hat. Baust du diesen Graphen aus echten Straßen und Knoten, erscheint oft ein vierter günstiger Weg aus der Kombinatorik. Ein Ziel findet einen dritten günstigen Heimweg, der im Budget bleibt, und die Lücke schließt sich. Genau dieser zusätzliche Weg war das Scheitern, das das Modell in den ersten drei Versuchen berichtete. Ein sauberes, symmetrisches Gadget, das eine 30 Jahre alte Vermutung in acht Zeilen Python bricht, wäre zu schön, um wahr zu sein – und ist es auch. Der obige Code beweist, dass die Prüfung korrekt ist und die Ziel-Eigenschaft real. Ob ein gegebener Graph diese Eigenschaft tatsächlich hat – ohne Lecks –, ist der harte Teil. Deshalb ist Rybins echtes Beispiel ein fein abgestimmter Punkt in einer Parameterfamilie und kein hübsches Dreieck.

Was noch offen ist

Es gibt noch kein formales Paper. Rybin hat das Gespräch und die Konstruktion geteilt; beides hat nicht den Begutachtungsprozess durchlaufen, der der mathematischen Community erlauben würde, die Vermutung offiziell zu schließen.

Den exakt veröffentlichten Graphen hat, soweit ich sehe, noch niemand unabhängig aus einer Primärquelle neu aufgebaut. Die kursierenden Zahlen stammen aus seinem Post und dem geteilten Transkript. Mehrere Forschende haben seine Rechnungen geprüft und als konsistent bezeichnet, und eine Person zeigte, dass sein Beispiel in eine unendliche Drei-Parameter-Familie auf denselben Knoten eingebettet ist – was das Ergebnis reichhaltiger machen würde als einen einzelnen Glückstreffer. Ermutigend, aber das ist informelle Community-Prüfung, kein Gutachten. Behandle die 58-zu-60 als gut gestützte Behauptung, nicht als feststehende Tatsache.

Der Überlastungs-Satz von 1999 bleibt davon unberührt.

Teil eines Musters

Diese Geschichte ist kein Einzelfall. Es ist die dritte Vermutung innerhalb von etwa drei Monaten, die mit KI-Unterstützung gefallen sein soll – und das Muster ist beachtenswert.

Am 20. Juli soll Claude Fable 5 dem Mathematiker Levent Alpöge geholfen haben, ein Gegenbeispiel zur Jacobischen Vermutung zu finden, einem 87 Jahre alten Problem. Davor hieß es im Mai, ein OpenAI-Modell habe die 80 Jahre alte Erdős-Einheitsabstandsvermutung widerlegt. In derselben Woche wie diese Nachricht löste ein Columbia-Doktorand mit GPT-5.6 und einem strukturierten Codex-Workflow sechs offene Erdős-Probleme in fünf Tagen. Der rote Faden, wie es ein Forscher formulierte: Diese Systeme sind besser im Widerlegen als im Beweisen. Ein Gegenbeispiel ist ein einzelner Zeuge, den man prüfen kann; ein Beweis muss alle Fälle abdecken. Diese Asymmetrie scheint zu entscheiden, welche Probleme zuerst fallen.

Die praktische Erkenntnis ist nicht „KI löst Mathe“. Was wir sehen, ist KI als geduldige, kombinatorisch erschöpfende Suchpartnerin: eine, die Parameterfamilien aufzählen, Fehlermodi über Versuche hinweg im Arbeitsgedächtnis halten und die Wahrheit sagen kann, wenn eine Konstruktion nicht schließt. Das ist eine spezifische, nützliche Fähigkeit. Und wenn du verstehen willst, wo sie als Nächstes einschlagen könnte, stell nicht die Frage, welche Vermutungen am ältesten sind, sondern welche sich durch einen einzigen überprüfbaren Zeugen brechen lassen.