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

Op 22 juli 2026 plaatste Dmitry Rybin een claim op X waar een bepaald type lezer z'n koffie voor 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 kleine graaf. 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 precies daar 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 vanaf nul te reproduceren, snap je meteen waarom dit soort problemen lastig zijn zodra je reconstructie begint te lekken.

Het korte antwoord

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

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. Reproduceerbaar rekenwerk en een geaccepteerd bewijs zijn echter verschillende dingen, en de afstand daartussen is het hele verhaal van dit artikel.

Wat is het Dinitz-Garg-Goemans-vermoeden?

Voor we kunnen waarderen wat er gevallen is, of zou kunnen zijn, moeten we begrijpen wat het vermoeden daadwerkelijk zegt.

Stel je een magazijn voor dat bestellingen verstuurt naar drie steden 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 fractionele routering, en die is flexibel; die vindt meestal een goedkoper padenset. Maar veel echte vracht kun je niet splitsen. Eén order, één truck, één weg, van begin tot eind. Dat is onsplitsbare stroom, en zo werkt een vrachtorder, een netwerkpakket of een container in de praktijk.

De vraag waar men sinds 1999 op kauwt, is simpel te stellen. Als er een goedkope gesplitste routering bestaat, kun je dan altijd een onsplitsbare routering vinden die óók goedkoop is zonder de wegen te zwaar te belasten?

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

De stelling vs. het vermoeden

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

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

Wat Goemans afzonderlijk heeft vermoed is de sterkere, kostengevoelige versie: dat dezelfde omzetting tegelijk de totale kosten laag kan houden én de congestie kan begrenzen. Congestie en kosten, beide begrensd, in één routering. De stelling over alleen congestie is veilig. Het kosten-plus-congestievermoeden is het stuk dat volgens Rybin is gevallen. Als je één zin uit dit stuk meeneemt, laat het die zijn. Veel opgewonden berichtgeving verwisselt ze stilletjes, en het verschil ertussen ís precies de wiskundige kloof waar 30 jaar over gedaan is.

Wat GPT-5.6 daadwerkelijk 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 manieren 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 willen routeren, overstroomt een ruggengraatweg. Duw je dat ver genoeg, dan kan in elke geldige onsplitsbare routering slechts één terminal z'n goedkope pad nemen. De rest wordt gedwongen naar dure directe paden, en de kosten lopen op. De fractionele flow, vrij om te splitsen, spreidt elke vraag over beide paden en glipt 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 paargewijze conflicten, niet kunnen reproduceren uit een primaire bron. Zijn transcript beschrijft een specifiek punt in een parameterfamilie, en de wijd gedeelde "zeven-knooppunten"-beschrijving is een abstractie daarvan, geen 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 wél kan doen, is je een zelfcontained instantie geven die hetzelfde mechanisme laat zien, klein genoeg om brute-force te checken, zodat je met eigen ogen ziet hoe "fractioneel verslaat elke legale onsplitsbare" eruitziet. 

Vier prompts, meerdere uren

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

Het chatlog dat Rybin deelde laat zien dat het model eerst faalde, en correct faalde. De openingsprompt vroeg om een gestructureerd tegenvoorbeeld. Het werkte het grootste deel van een uur en kwam met lege handen terug, en zei ronduit dat presenteren wat het had als geldig tegenvoorbeeld onwaar zou zijn.

Opdracht om door te gaan: het draaide opnieuw, en meldde opnieuw niets, met een beschrijving hoe elke veelbelovende constructie steeds een verborgen extra routeringsoptie bleek te hebben die, zodra alle paden werden opgesomd, de scheiding tussen kosten en congestie vernietigde. Een derde prompt met de vraag 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 loopt en daar eerlijk over is. De specifieke muur waar het telkens tegenaan liep — er verschijnt een extra route en die verpest de scheiding — is precies wat de uiteindelijke constructie voorkwam, door elke terminal vast te pinnen op precies twee paden zodat de hele routeringsruimte uit acht opties bestaat die je met de hand kunt opsommen. Onthoud die faalmodus. Jij gaat er zo zelf tegenaan lopen.

De vierde prompt, naar verluidt iets als "genoeg van je falen, rond dit af met een complete onvoorwaardelijke tegenvoorbeeldconstructie," is degene die de werkende constructie opleverde, samen met bewijscertificaten, een enumeratieprogramma en volledige LaTeX. Het geduld deed ertoe. Dat gold ook voor de eerdere weigeringen; het waren eerlijke zelfassessments.

Check het zelf

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

Een korte kanttekening voor de code. Wat volgt is niet Rybins graaf. Het is een schematische instantie die ik heb gebouwd om eerlijk te zijn: één waarin elke terminal precies twee routes heeft, de rekensom klopt en de kloof 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 direct na het draaien uit waarom.

De setup: drie terminals, elk versturen 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 ervan vecht over z'n eigen private knelpuntweg: weg A wordt gedeeld door terminals 1 en 2, weg B door terminals 1 en 3, weg C door terminals 2 en 3. In de fractionele flow 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 4 + 4 = 8 eenheden fractioneel, en het congestiebudget is die belasting plus D, dus 18.

Kijk nu wat onsplitsbare routering daarmee doet. Twee terminals die allebei goedkoop gaan, dumpen 10 + 10 = 20 eenheden op hun gedeelde weg, boven het budget van 18. Dus maximaal één terminal kan goedkoop routeren; de andere twee betalen elk 30. Minimale legale onsplitsbare kost: 60. Tegenover een fractionele 54. Er bestaan acht routeringen, dus we checken ze 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)")

Draai het en je krijgt een fractionele kost van 54, een minimale legale onsplitsbare kost van 60, en een kloof van 6. De drie overladen rijen zijn de drie paarconflicten; de enige routeringen die overblijven, houden hooguit één terminal goedkoop.

Dus is het vermoeden dood? Nog niet, en dit is het deel dat ik beloofde uit te leggen. Die opsomming van acht rijen vertelt alleen de waarheid als elke terminal echt twee routes heeft en niet meer. Bouw deze graaf uit echte wegen en knooppunten, en er duikt uit de combinatoriek vaak een vierde goedkope route op. Een terminal vindt een derde manier naar huis die goedkoop is en binnen budget blijft, en de kloof sluit. Die extra route is precies de mislukking die het model bij de eerste drie pogingen rapporteerde. Een schoon, symmetrisch gadget dat een 30 jaar oud vermoeden breekt in acht regels Python is te mooi om waar te zijn, en dat is het ook. De code hierboven bewijst dat de check deugt en dat de gezochte eigenschap echt is. Of een gegeven graaf die eigenschap daadwerkelijk heeft, zonder lekken, is het moeilijke deel, en daarom is Rybins echte instantie een getuned punt in een parameterfamilie in plaats van een keurige driehoek.

Wat nog onopgelost is

Er is nog geen formeel paper verschenen. Rybin deelde het gesprek en de constructie; geen van beide is door het refereeproces 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 iemand 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 referee-rapport. Behandel de 58-vs-60 als een goed onderbouwde claim, geen vastgesteld feit.

De congestiestelling uit 1999 blijft door dit alles onaangetast.

Onderdeel van een patroon

Dit verhaal staat niet op zichzelf. Het is de derde keer in ongeveer drie maanden dat een vermoeden zou zijn gevallen met AI-assistentie, en dat patroon is het benoemen waard.

Op 20 juli zou Claude Fable 5 wiskundige Levent Alpöge hebben geholpen een tegenvoorbeeld voor het Jacobiaan-vermoeden te vinden, een 87 jaar oud probleem. Daarvoor, in mei, zou een OpenAI-model het 80 jaar oude unit-distance-vermoeden van Erdős hebben weerlegd. In dezelfde week als dit nieuws gebruikte een promovendus van 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 alle gevallen 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 opsommen, faalmodi in het werkgeheugen kan houden over pogingen heen, en de waarheid kan vertellen wanneer 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 kunnen worden gebroken door één controleerbare getuige.