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

Am 22. Juli 2026 postete Dmitry Rybin auf X eine Behauptung, bei der eine bestimmte Art Mensch den Kaffee abstellte: GPT-5.6 Pro hatte ein Gegenbeispiel zur Dinitz-Garg-Goemans-Vermutung erzeugt, einer seit rund 30 Jahren offenen Frage in der kombinatorischen Optimierung. Der Machbarkeitsnachweis war ein kleiner Graph. Fraktionierte Flusskosten 58, unteilbare Flusskosten 60. Zwei Punkte, drei Jahrzehnte, vier Prompts.

Die meisten Berichte wiederholen die Zahlen, ohne den Mechanismus dahinter zu zeigen, und genau dort liegt die eigentliche Lektion. Dort muss ich auch ehrlich sagen, was bereits verifiziert ist und was nicht. Kurzfassung: Die Konzepte sind solide, die Neuigkeit ist eine Behauptung und noch kein Theorem, und wenn du dich hinsetzt, um den genauen Graphen von Grund auf zu rekonstruieren, merkst du, warum solche Probleme hart sind – in dem Moment, in dem deine Rekonstruktion zu lecken beginnt.

Die Kurzantwort

Rybin berichtet, dass GPT-5.6 Pro, gesteuert durch vier Prompts mit insgesamt unter 60 Wörtern, ein angebliches Gegenbeispiel zu Goemans' Kostenvermutung geliefert hat – ein seit etwa 1999 offenes Problem. Sein Beispiel ist ein kleiner gerichteter Graph mit einer Quelle und drei Zielknoten. Er gibt an, dass die aufteilbare (fraktionierte) Routung 58 kostet, während jede unteilbare Routung, die die zulässige Auslastung einhält, mindestens 60 kostet. Diese Zweipunkte-Lücke reicht, wenn sie einer formalen Prüfung standhält, aus, um die Vermutung zu kippen.

Das Ganze hat noch kein Peer-Review durchlaufen. Rybin hat das komplette ChatGPT-Gespräch veröffentlicht, sodass jede Person die Konstruktion lesen kann, und mehrere haben seine Rechnungen geprüft und für stimmig befunden. Nachrechenbare Arithmetik und ein akzeptierter Beweis sind allerdings zwei verschiedene Dinge, und der Abstand dazwischen ist die gesamte Geschichte dieses Artikels.

Was ist die Dinitz-Garg-Goemans-Vermutung?

Bevor wir würdigen können, was gefallen ist – oder gefallen sein könnte –, müssen wir verstehen, was die Vermutung tatsächlich besagt.

Stell dir ein Lagerhaus vor, das Bestellungen über ein Straßennetz an drei Städte verschickt. Wenn du eine Sendung aufteilen darfst, kannst du eine Hälfte über die eine Straße und die andere Hälfte über eine andere schicken. Das ist fraktioniertes Routing und flexibel; meist findet es günstigere Pfade. Aber viele reale Frachten lassen sich nicht teilen. Eine Bestellung, ein Lkw, eine Straße, von Anfang bis Ende. Das ist unteilbarer Fluss – und genau so verhalten sich Frachtaufträge, Netzpakete oder Container in der Realität.

Die seit 1999 diskutierte Frage ist leicht zu formulieren: Wenn es eine günstige fraktionierte Routung gibt, lässt sich dann immer eine unteilbare Routung finden, die ebenfalls günstig ist, ohne die Straßen zu stark zu überlasten?

Yefim Dinitz, Naveen Garg und Michel Goemans haben die halbe Frage geklärt. Die andere Hälfte ist der Teil, den GPT-5.6 angegriffen hat. Um zu verstehen, warum dieser Unterschied enorm wichtig ist, müssen wir präzise werden.

Der Satz vs. die Vermutung

Das ist der Unterschied, den die meisten Berichte verwischen. Ich lege ihn einmal genau dar und beziehe mich danach im Text darauf.

Dinitz, Garg und Goemans haben einen Ergebnis zur Überlastung bewiesen: Ausgehend von einem gültigen fraktionierten Fluss lässt er sich stets in einen unteilbaren umwandeln, ohne die Kapazität irgendeiner Straße um mehr als die größte Einzelnachfrage – nenn sie D – zu überschreiten. Dieser Satz steht nicht infrage und stand es nie.

Was Goemans zusätzlich vermutete, ist die stärkere, kostenbewusste Version: dass dieselbe Umwandlung gleichzeitig die Gesamtkosten niedrig halten könnte, während sie die Überlastung begrenzt. Überlastung und Kosten, beide beschränkt, in einer Routung. Der reine Überlastungs-Satz ist unangefochten. Die Kosten-plus-Überlastungs-Vermutung ist das Stück, das laut Rybin gefallen ist. Wenn du nur einen Satz aus diesem Beitrag mitnimmst, dann diesen. Viel der euphorischen Berichterstattung tauscht die beiden 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, um es in einem Absatz zu beschreiben: Eine Quelle, ein paar Zwischenknoten, die eine gemeinsame „Wirbelsäule“ bilden, und drei Zielknoten mit jeweiliger Nachfrage. Jeder Zielknoten hat zwei Wege nach Hause: einen teuren Direktweg oder einen kostenlosen Umweg über die gemeinsame Wirbelsäule.

Die Spannung ist strukturell. Die günstigen Umwege konkurrieren um Platz auf der Wirbelsäule. Versuchen zu viele Ziele gleichzeitig günstig zu routen, läuft eine Straßenkante der Wirbelsäule über. Treibt man das weit genug, kann in jeder gültigen unteilbaren Routung nur ein Zielknoten den günstigen Weg nehmen. Die anderen werden auf ihre teuren Direktwege gezwungen – die Kosten steigen. Der fraktionierte Fluss, frei zu splitten, 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 hier offen über eine Grenze: Ich konnte Rybins exakten Graphen – die konkreten Kapazitäten und paarweisen Konflikte – nicht aus einer Primärquelle reproduzieren. Sein Transkript beschreibt einen bestimmten Punkt in einer Parameterfamilie, und die vielgeteilte „Sieben-Knoten“-Beschreibung ist eine Abstraktion davon, keine Konstruktion, die ich Kante für Kante verifiziert habe. Ich werde also keine saubere Herleitung der 58 inszenieren und so tun, als sei sie seine. Was ich kann, ist dir ein in sich geschlossenes Beispiel zu geben, das denselben Mechanismus zeigt – klein genug, um es per Brute-Force zu prüfen –, damit du mit eigenen Augen siehst, wie „fraktioniert schlägt jede zulässige unteilbare Routung“ aussieht. 

Vier Prompts, mehrere Stunden

Die Anzahl der Prompts ist das Uninteressanteste an dieser Geschichte – auch wenn genau dieser Teil viral ging.

Das von Rybin geteilte Chatprotokoll zeigt, dass das Modell zunächst scheiterte – und zwar treffend scheiterte. Die erste Aufforderung bat um ein strukturiertes Gegenbeispiel. Es arbeitete fast eine Stunde und kam mit leeren Händen zurück – mit der klaren Aussage, dass es falsch wäre, das Erarbeitete als gültiges Gegenbeispiel zu präsentieren.

Aufgefordert, weiterzumachen, lief es erneut und berichtete wieder nichts – mit der Erklärung, dass jede vielversprechende Konstruktion bei vollständiger Pfadauflistung eine versteckte zusätzliche Routing-Option hervorbrachte, die die Trennung von Kosten und Überlastung zerstörte. Ein dritter Prompt mit der Bitte um eine sauberere Strategie lieferte einen engeren Rahmen – aber immer noch kein fertiges Ergebnis.

Das ist nicht „vier Prompts und 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 prallte – es erscheint ein zusätzlicher Pfad und ruiniert die Trennung –, ist genau das, was die finale Konstruktion verhindert, indem sie jeden Zielknoten auf genau zwei Pfade festnagelt, sodass der gesamte Routingraum aus acht Optionen besteht, die du von Hand aufzählen kannst. Behalte dieses Fehlermuster im Kopf. Du wirst gleich selbst darauf stoßen.

Der vierte Prompt – dem Vernehmen nach etwas wie „genug von deinen Fehlversuchen, bitte liefere ein vollständiges, bedingungsloses Gegenbeispiel“ – lieferte dann die funktionierende Konstruktion, samt Beweiszertifikaten, 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 Newspost nicht kann: Dich die Verifikation selbst ausführen lassen.

Ein kurzer Hinweis vor dem Code: Was folgt, ist nicht Rybins Graph. Es ist ein schematisches Beispiel, das ich bewusst so gebaut habe, dass jeder Zielknoten genau zwei Pfade hat, die Rechnung aufgeht und die Lücke real ist. Es zeigt dir die Form eines solchen Gegenbeispiels und die Prüftechnik. Für sich genommen widerlegt es nichts – warum, erkläre ich direkt nach dem Lauf.

Das Setup: drei Zielknoten mit jeweils 10 Einheiten Nachfrage, also ist die größte Nachfrage D gleich 10. Jeder 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, private Engpass-Straße konkurriert: Straße A wird von Ziel 1 und 2 geteilt, Straße B von 1 und 3, Straße C von 2 und 3. Im fraktionierten Fluss schickt jeder Zielknoten 2/5 seiner Nachfrage günstig und 3/5 teuer, was 30 x 3/5 x 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 Routung daraus macht. Gehen zwei Zielknoten beide günstig, kippen 10 + 10 = 20 Einheiten auf ihre gemeinsame Straße – über das Budget von 18. Also kann höchstens ein Zielknoten günstig routen; die anderen zwei zahlen jeweils 30. Minimale zulässige unteilbare Kosten: 60. Gegenüber fraktionierten 54. Es gibt acht Routings, also prüfen wir sie 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)")

Wenn du es ausführst, erhältst du 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; die einzigen zulässigen Routings halten höchstens einen Zielknoten günstig.

Also ist die Vermutung tot? Noch nicht, und das ist der Teil, den ich versprochen habe zu erklären. Diese Acht-Zeilen-Enumeration sagt nur dann die Wahrheit, wenn jeder Zielknoten wirklich genau zwei Wege hat und keinen weiteren. Baust du diesen Graphen aus echten Straßen und Knoten, taucht aus der Kombinatorik oft ein vierter günstiger Weg auf. Ein Ziel findet einen dritten Heimweg, der günstig bleibt und im Budget liegt – und die Lücke schließt sich. Genau diese zusätzliche Route war das Scheitern, das das Modell in seinen 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 solide ist und die Ziel-Eigenschaft real. Ob ein gegebener Graph diese Eigenschaft tatsächlich ohne Lecks hat, ist der harte Teil – und der Grund, warum Rybins reales Beispiel ein fein abgestimmter Punkt in einer Parameterfamilie ist und kein hübsches Dreieck.

Was noch offen ist

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

Den exakt veröffentlichten Graphen konnte ich nirgends unabhängig aus einer Primärquelle rekonstruiert finden. 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 reicher machen würde als einen einzelnen Glückstreffer. Ermutigend, aber das ist informelle Community-Prüfung, kein Gutachten. Behandle die 58-gegen-60 als gut gestützte Behauptung, nicht als gesicherte Tatsache.

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

Teil eines Musters

Diese Geschichte ist kein Einzelfall. Es ist die dritte Vermutung innerhalb von etwa drei Monaten, die angeblich mit KI-Unterstützung gefallen ist – und das Muster lohnt sich zu betrachten.

Am 20. Juli soll Claude Fable 5 den Mathematiker Levent Alpöge dabei unterstützt haben, ein Gegenbeispiel zur Jacobischen Vermutung zu finden – einem 87 Jahre alten Problem. Davor, im Mai, soll ein OpenAI-Modell die 80 Jahre alte Erdős-Einheitsabstandsvermutung widerlegt haben. In derselben Woche wie diese Nachricht löste ein PhD-Student der Columbia University 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 ausdrückte: 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 lautet nicht „KI löst Mathematik“. Was wir beobachten, 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 zuschlagen könnte, frag dich nicht, welche Vermutungen am ältesten sind, sondern welche sich durch einen einzigen überprüfbaren Zeugen kippen lassen.