GPT-5.6 en het Dinitz-Garg-Goemans-vermoeden

Op 22 juli 2026 plaatste Dmitry Rybin een claim op X waardoor een bepaald soort mens z'n koffie neerzette: GPT-5.6 Pro had een tegenvoorbeeld geproduceerd voor het Dinitz-Garg-Goemans-vermoeden, al zo'n 30 jaar open in combinatorische optimalisatie. Het proof-of-concept was één klein graafje. Fractionele stroom kost 58, onsplitsbare stroom kost 60. Twee punten, drie decennia, vier prompts.

De meeste berichtgeving herhaalt de getallen zonder het mechanisme erachter te tonen, en juist in dat mechanisme zit de echte les. Het is ook waar ik eerlijk met je moet zijn over wat wel en niet is geverifieerd. Korte versie: de concepten zijn solide, het nieuws is een claim en nog geen stelling, en als je gaat zitten om de exacte graaf helemaal from scratch te reproduceren, leer je meteen waarom dit soort problemen moeilijk zijn zodra je reconstructie begint te lekken.

Het Korte Antwoord

Rybin meldt dat GPT-5.6 Pro, gestuurd door vier prompts van in totaal minder dan 60 woorden, een vermeend tegenvoorbeeld opleverde voor Goemans' kostenvermoeden, een probleem dat sinds ongeveer 1999 openstaat. Zijn instantie is een kleine gerichte graaf met één bron en drie afleverterminals. Hij stelt dat het splitsbare (fractionele) routeren 58 kost, terwijl elke onsplitsbare routering die de congestie binnen het toegestane budget houdt minstens 60 kost. Dat tweepunts gat, als het de formele toetsing doorstaat, is genoeg om het vermoeden onderuit te halen.

Het is niet peer-reviewed. Rybin publiceerde het volledige ChatGPT-gesprek zodat iedereen de constructie kan lezen, en meerdere mensen hebben zijn rekenwerk gecontroleerd en consistent bevonden. Reproduceerbare rekenkunst en een geaccepteerd bewijs zijn echter verschillende beesten, en de afstand ertussen is het hele verhaal van dit artikel.

Wat is het Dinitz-Garg-Goemans-vermoeden?

Voordat we kunnen waarderen wat gevallen is, of gevallen zou kunnen zijn, moeten we begrijpen wat het vermoeden eigenlijk zegt.

Stel je een magazijn voor dat bestellingen naar drie steden verzendt via een wegennet. Als je een zending mag splitsen, kun je de helft via de ene weg en de helft via een andere sturen. Dat is fractioneel routeren, en het is flexibel; het vindt meestal een goedkoper padenset. Maar veel echte vracht kun je niet splitsen. Eén order, één vrachtwagen, één weg, van begin tot eind. Dat is onsplitsbare stroom, en dat is wat een vrachtorder, een netwerkpakket of een container in de praktijk moet doen.

De vraag waar men sinds 1999 op kauwt, is simpel te formuleren. Als er een goedkope, splitsbare routering bestaat, kun je dan altijd een onsplitsbare routering vinden die ook goedkoop is zonder de wegen al te zwaar te overbelasten?

Yefim Dinitz, Naveen Garg en Michel Goemans hebben de helft ervan opgelost. De andere helft is het deel waar GPT-5.6 op mikte. Om te begrijpen waarom dat onderscheid enorm belangrijk is, moeten we precies zijn.

De Stelling versus het Vermoeden

Dit is het onderscheid dat de meeste stukken laten vervagen, dus ik ben er één keer precies over en leun er daarna op voor de rest van het artikel.

Dinitz, Garg en Goemans hebben bewezen dat je, gegeven een geldige fractionele stroom, die altijd kunt omzetten naar een onsplitsbare zonder de capaciteit van een weg met meer dan de grootste enkele vraag te overschrijden; noem dat getal D. Die stelling staat niet ter discussie en heeft dat ook nooit gedaan.

Wat Goemans apart heeft vermoed is de sterkere, kostenbewuste versie: dat dezelfde omzetting de totale kosten laag zou kunnen houden terwijl hij tegelijkertijd de congestie beperkt. Congestie en kosten, beide begrensd, in één routering. De stelling over alleen congestie is onaangetast. Het kosten-plus-congestie-vermoeden is het stuk waarvan Rybin zegt dat het gevallen is. Als je één zin uit dit stuk meeneemt, laat het die dan zijn. Veel van de opgewonden berichtgeving wisselt de twee stilletjes om, en het verschil ertussen is precies de wiskundige kloof die 30 jaar kostte om te dichten.

Wat GPT-5.6 Eigenlijk Bouwde

Rybins instantie is klein genoeg om in een alinea te beschrijven. Een bron, een paar tussenknooppunten die samen een gedeelde "ruggengraat" vormen, en drie terminals, elk met een vraag. Elke terminal heeft twee wegen naar huis: een dure directe route, of een gratis omweg via de gedeelde ruggengraat.

De spanning is structureel. De goedkope omwegen concurreren om ruimte op de ruggengraat, dus als te veel terminals tegelijk goedkoop proberen te routeren, loopt een ruggengraatsweg vol. Duw je dat ver genoeg, dan kan in elke geldige onsplitsbare routering maar één terminal z'n goedkope pad nemen. De rest wordt gedwongen naar hun dure directe paden, en de kosten lopen op. De fractionele stroom, vrij om te splitsen, spreidt elke vraag over beide paden en glipt zo onder elke capaciteit door. Zo krijg je een fractionele kost onder de goedkoopste legale onsplitsbare kost. Rybins cijfers voor zijn instantie zijn 58 en 60.

Ik ben eerlijk over een beperking. Ik heb Rybins exacte graaf, de specifieke capaciteiten en de paarsgewijze conflicten, niet uit een primaire bron kunnen reproduceren. Zijn transcript beschrijft een specifiek punt in een parameterfamilie, en de wijd gedeelde "zeven-knooppunten"-beschrijving is een abstractie ervan, niet een constructie die ik rand voor rand heb geverifieerd. Dus ik ga geen nette afleiding van 58 opvoeren en doen alsof die van hem is. Wat ik wel kan doen, is je een zelfstandige instantie geven die hetzelfde mechanisme laat zien, klein genoeg om met brute force te controleren, zodat je met eigen ogen ziet hoe "fractioneel verslaat elke legale onsplitsbare" eruitziet. 

Vier Prompts, Uren Werk

Het aantal prompts is het minst interessante aan dit verhaal, al is dat het deel dat viraal ging.

De chatlog die Rybin deelde laat zien dat het model eerst faalde, en het faalde accuraat. De openingsprompt vroeg om een gestructureerd tegenvoorbeeld. Het werkte ruim een uur en kwam met lege handen terug, met de mededeling dat presenteren wat het had als een geldig tegenvoorbeeld onwaar zou zijn.

Opdracht om door te gaan, het draaide opnieuw, en rapporteerde opnieuw niets, met beschrijving hoe elke veelbelovende constructie steeds een verborgen extra routeringsoptie bleek te hebben die de scheiding tussen kosten en congestie vernietigde zodra alle paden waren opgesomd. Een derde prompt met het verzoek om een schonere strategie leverde een smaller raamwerk op en nog steeds geen eindresultaat.

Dat is niet "vier prompts, klaar." Dat zijn uren van een model dat tegen muren op loopt en daar eerlijk over is. De specifieke muur waar het steeds tegenaan botste — er verschijnt een extra route en die verknoeit de scheiding — is precies wat de uiteindelijke constructie moest voorkomen, door elke terminal vast te pinnen op precies twee paden zodat de hele routeringsruimte acht opties is die je met de hand kunt opsommen. Houd die faalmodus in gedachten. Je gaat er zo zelf tegenaan lopen.

De vierde prompt, naar verluidt iets in de trant van "ik heb genoeg van je falen, rond dit af met een compleet onvoorwaardelijk tegenvoorbeeld," is degene die de werkende constructie opleverde, plus bewijscertificaten, een enumeratieprogramma en volledige LaTeX. Het geduld was belangrijk. Net als de eerdere weigeringen; die waren eerlijke zelfbeoordelingen.

Controleer Het Zelf

Hier kan DataCamp iets doen wat een nieuwsbericht niet kan: je de verificatie laten uitvoeren.

Een korte kanttekening vóór de code. Wat volgt is niet Rybins graaf. Het is een schematische instantie die ik eerlijk heb opgebouwd, eentje waarin elke terminal echt precies twee routes heeft, de sommen kloppen en het gat echt is. Het laat je de vorm zien van zo'n tegenvoorbeeld en de techniek om er één te controleren. Het weerlegt op zichzelf niets, en ik leg meteen na het draaien uit waarom.

De opzet: drie terminals, elk verzendt 10 eenheden, dus de grootste vraag D is 10. Elk heeft een dure directe route (kost 30) en een gratis goedkope route. De goedkope routes zijn zo gerangschikt dat elk paar daarvan vecht om z'n eigen private knelpuntweg: weg A wordt gedeeld door terminals 1 en 2, weg B door 1 en 3, weg C door 2 en 3. In de fractionele stroom stuurt elke terminal 2/5 van z'n vraag goedkoop en 3/5 duur, wat kost 30 x 3/5 x 3 = 54. Elke weg draagt dan fractioneel 4 + 4 = 8 eenheden, en het congestiebudget is die belasting plus D, dus 18.

Kijk nu wat onsplitsbaar routeren daarmee doet. Twee terminals die allebei goedkoop gaan, dumpen 10 + 10 = 20 eenheden op hun gedeelde weg, boven het budget van 18. Dus hoogstens één terminal kan goedkoop routeren; de andere twee betalen elk 30. Minimale legale onsplitsbare kosten: 60. Tegenover een fractionele 54. Er bestaan acht routeringen, dus we checken ze gewoon allemaal:

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

Voer het uit en je krijgt een fractionele kost van 54, een minimale legale onsplitsbare kost van 60, en een gat van 6. De drie overladen rijen zijn de drie paarsgewijze conflicten; de enige routeringen die overblijven, houden hoogstens één terminal goedkoop.

Dus is het vermoeden dood? Niet helemaal, en dit is het deel dat ik beloofde uit te leggen. Die acht-rijen-enumeratie vertelt alleen de waarheid als elke terminal echt twee routes heeft en niet meer. Bouw deze graaf op uit echte wegen en knooppunten, en er duikt vaak een vierde goedkope route op uit de combinatoriek. Een terminal vindt een derde weg naar huis die goedkoop is en binnen budget blijft, en het gat sluit. Die extra route is precies de mislukking die het model bij z'n eerste drie pogingen meldde. Een schoon, symmetrisch hulpstuk dat een 30 jaar oud vermoeden breekt in acht regels Python zou te mooi zijn om waar te zijn, en dat is het ook. De code hierboven bewijst dat de controle deugt en dat de beoogde eigenschap echt is. Of een gegeven graaf die eigenschap daadwerkelijk heeft, zonder lekken, is het moeilijke deel, en het is de reden dat Rybins echte instantie een getunede punt in een parameterfamilie is en geen keurig driehoekje.

Wat Nog Onbeslist Is

Er is nog geen formeel paper verschenen. Rybin deelde het gesprek en de constructie; geen van beide is door het referentieproces gegaan dat de wiskundige gemeenschap het vermoeden officieel zou laten sluiten.

De exact gepubliceerde graaf is, voor zover ik kan vinden, niet onafhankelijk opnieuw opgebouwd uit een primaire bron. De rondgaande getallen komen uit zijn post en het gedeelde transcript. Verschillende onderzoekers hebben zijn rekenwerk gecontroleerd en consistent genoemd, en één liet zien dat zijn instantie binnen een oneindige drie-parameterfamilie op dezelfde knooppunten ligt, wat het resultaat rijker zou maken dan één enkel gelukkig toeval. Bemoedigend, maar dat is informele community-checking, geen referentierapport. Behandel de 58-vs-60 als een goed onderbouwde claim, geen vaststaand feit.

De congestiestelling uit 1999 blijft door dit alles onaangetast.

Deel van een Patroon

Dit verhaal staat niet op zichzelf. Het is het derde vermoeden dat in ongeveer drie maanden naar verluidt door AI-assistentie is gevallen, en het patroon is het overdenken waard.

Op 20 juli zou Claude Fable 5 wiskundige Levent Alpöge hebben geholpen een tegenvoorbeeld voor het Jacobiaanse vermoeden te vinden, een 87 jaar oud probleem. Daarvoor, in mei, zou een OpenAI-model het 80 jaar oude Erdős unit-distance-vermoeden hebben weerlegd. In dezelfde week als dit nieuws gebruikte een promovendus in Columbia GPT-5.6 met een gestructureerde Codex-workflow om zes open Erdős-problemen in vijf dagen op te lossen. De rode draad, zoals een onderzoeker het verwoordde, is dat deze systemen beter zijn in weerleggen dan in bewijzen. Een tegenvoorbeeld is één getuige die je kunt checken; een bewijs moet elk geval afdekken. Die asymmetrie lijkt te bepalen welke problemen als eerste vallen.

De praktische les is niet "AI lost wiskunde op." Wat we zien, is AI als geduldige, combinatorisch uitputtende zoekpartner: eentje die parameterfamilies kan enumereren, faalmodi in het werkgeheugen kan houden over pogingen heen, en de waarheid vertelt als een constructie niet sluit. Dat is een specifieke, nuttige capaciteit. En als je wilt begrijpen waar het waarschijnlijk als volgende toeslaat, is de vraag niet welke vermoedens het oudst zijn, maar welke door één controleerbare getuige kunnen worden gebroken.