GPT-5.6 och Dinitz–Garg–Goemans-förmodan

Den 22 juli 2026 postade Dmitry Rybin ett påstående på X som fick en viss sorts personer att lägga ner kaffet: GPT-5.6 Pro hade tagit fram ett motexempel till Dinitz–Garg–Goemans-förmodan, ett öppet problem inom kombinatorisk optimering i omkring 30 år. Beviset på konceptet var en liten graf. Fraktionerad flödeskostnad 58, odelbar flödeskostnad 60. Två poäng, tre decennier, fyra uppmaningar.

De flesta artiklar upprepar siffrorna utan att visa mekanismen bakom, och det är i mekanismen som den verkliga lärdomen finns. Det är också där jag måste vara rak med dig om vad som har verifierats och vad som inte har det. Den korta versionen: koncepten är solida, nyheten är ett påstående och ännu ingen sats, och om du sätter dig för att återskapa exakt den grafen från grunden lär du dig varför problem som detta är svåra i samma ögonblick som din rekonstruktion börjar läcka.

Det snabba svaret

Rybin rapporterar att GPT-5.6 Pro, styrd av fyra uppmaningar på under 60 ord totalt, tog fram ett påstått motexempel till Goemans kostnadsförmodan, ett problem som varit öppet sedan ungefär 1999. Hans exempel är en liten riktad graf med en källa och tre leveransterminaler. Han anger att den delbara (fraktionerade) routingen kostar 58, medan varje odelbar routing som håller trängseln inom den tillåtna budgeten kostar minst 60. Det tvåpoängsglappet, om det överlever formell granskning, räcker för att sänka förmodan.

Det har inte genomgått peer review. Rybin publicerade hela ChatGPT-konversationen så att vem som helst kan läsa konstruktionen, och flera personer har kontrollerat hans aritmetik och funnit den konsekvent. Reproducerbar aritmetik och ett accepterat bevis är dock olika saker, och avståndet mellan dem är hela berättelsen i den här artikeln.

Vad är Dinitz–Garg–Goemans-förmodan?

Innan vi kan uppskatta vad som föll, eller kan ha gjort det, måste vi förstå vad förmodan faktiskt säger.

Föreställ dig ett lager som skickar order till tre städer via ett vägnät. Om du får dela upp en sändning kan du skicka halva ordern på en väg och halva på en annan. Det är fraktionerad routing, och den är flexibel; den hittar oftast ett billigare set av vägar. Men mycket verkligt gods kan inte delas. En order, en lastbil, en väg, från start till mål. Det är odelbart flöde, och det är vad en fraktorder, ett nätverkspaket eller en fraktcontainer faktiskt måste göra.

Frågan man har grubblat på sedan 1999 är enkel att formulera. Om en billig delbar routing finns, kan du alltid hitta en odelbar routing som också är billig utan att överlasta vägarna alltför mycket?

Yefim Dinitz, Naveen Garg och Michel Goemans löste halva problemet. Den andra halvan är den del som GPT-5.6 gav sig på. För att förstå varför den distinktionen spelar enorm roll måste vi vara precisa.

Satsen kontra förmodan

Detta är distinktionen som de flesta texter suddar ut, så jag ska vara noggrann en gång och sedan luta mig mot den i resten av artikeln.

Dinitz, Garg och Goemans bevisade ett trängselresultat: givet ett giltigt fraktionerat flöde kan du alltid konvertera det till ett odelbart utan att överskrida någon vägs kapacitet med mer än den största enskilda efterfrågan, kalla det talet D. Den satsen är inte ifrågasatt och har aldrig varit det.

Vad Goemans separat förmodade är den starkare, kostnadsmedvetna versionen: att samma konvertering samtidigt skulle kunna hålla nere totalkostnaden när den håller nere trängseln. Trängsel och kostnad, båda begränsade, i en och samma routing. Satsen om enbart trängsel är trygg. Förmodan om kostnad plus trängsel är den del som Rybin säger föll. Om du bara tar med dig en mening från den här texten, låt det bli den. Mycket av den upphetsade rapporteringen byter tyst ut de två, och skillnaden mellan dem är hela det matematiska glappet som tog 30 år att stänga.

Vad GPT-5.6 faktiskt byggde

Rybins exempel är tillräckligt litet för att beskrivas i ett stycke. En källa, några mellannoder som bildar en delad "ryggrad", och tre terminaler, var och en med en efterfrågan. Varje terminal har två vägar hem: en dyr direktväg eller en gratis omväg genom den delade ryggraden.

Spänningen är strukturell. De billiga omvägarna konkurrerar om plats på ryggraden, så om för många terminaler försöker rutta billigt samtidigt svämmar en ryggradsväg över. Pressas det tillräckligt långt kan bara en terminal ta sin billiga väg i en giltig odelbar routing. Resten tvingas in på sina dyra direktvägar, och kostnaden stiger. Det fraktionerade flödet, som får dela upp sig, sprider varje efterfrågan över båda vägarna och smiter under varje kapacitet samtidigt. Det är så du får en fraktionerad kostnad under den billigaste lagliga odelbara kostnaden. Rybins siffror för hans exempel är 58 och 60.

Jag ska vara ärlig med en begränsning här. Jag har inte kunnat återskapa Rybins exakta graf, de specifika kapaciteterna och de parvisa konflikterna, från en primärkälla. Hans utskrift beskriver en särskild punkt i en parameterfamilj, och den vida spridda beskrivningen av "sju noder" är en abstraktion av den, inte en konstruktion jag har verifierat kant för kant. Så jag tänker inte iscensätta en prydlig härledning av 58 och låtsas att den är hans. Vad jag kan göra är att ge dig ett självbärande exempel som visar samma mekanism, tillräckligt litet för att kontrollera med brute force, så att du med egna ögon kan se hur "fraktionerat slår varje laglig odelbar" ser ut. 

Fyra uppmaningar, flera timmar

Antalet uppmaningar är det minst intressanta med den här historien, även om det var den delen som blev viral.

Chattloggen Rybin delade visar att modellen misslyckades först, och misslyckades korrekt. Den första uppmaningen bad den hitta ett strukturerat motexempel. Den arbetade i bättre delen av en timme och kom tillbaka tomhänt, och sade rent ut att det vore fel att presentera det den hade som ett giltigt motexempel.

Uppmanad att fortsätta körde den igen, och rapporterade återigen inget, och beskrev hur varje lovande konstruktion hela tiden fick en dold extra routingmöjlighet som förstörde separationen mellan kostnad och trängsel när alla vägar väl räknades upp. En tredje uppmaning om en renare strategi gav en snävare ram men fortfarande inget färdigt resultat.

Det där är inte "fyra uppmaningar, klart." Det är timmar av en modell som kör in i väggar och berättar sanningen om dem. Den specifika väggen den gång på gång körde in i, en extra väg dyker upp och förstör separationen, är exakt vad den slutliga konstruktionen byggdes för att förhindra, genom att låsa varje terminal till precis två vägar så att hela routingsrymden är åtta alternativ du kan räkna upp för hand. Ha det felscenariot i minnet. Du kommer själv snart att stöta på det.

Den fjärde uppmaningen, enligt uppgift något i stil med "nu räcker det med misslyckanden, var snäll och avsluta med ett fullständigt ovillkorligt motexempel," är den som gav den fungerande konstruktionen, tillsammans med beviscertifikat, ett uppräkningsprogram och fullständig LaTeX. Tålamodet spelade roll. Det gjorde även de tidigare vägringarna; de var ärliga självbedömningar.

Kontrollera själv

Här kan DataCamps bevakning göra något som en nyhetspost inte kan: låta dig köra verifieringen.

En snabb brasklapp före koden. Det som följer är inte Rybins graf. Det är ett schematiskt exempel jag byggt för att vara ärligt, ett där varje terminal faktiskt har exakt två rutter, aritmetiken går ihop och glappet är verkligt. Det visar formen av ett sådant motexempel och tekniken för att kontrollera ett. Det motbevisar inte i sig något, och jag förklarar varför direkt efter att du kört det.

Upplägget: tre terminaler, var och en skickar 10 enheter, så den största efterfrågan D är 10. Var och en har en dyr direktväg (kostnad 30) och en gratis billig väg. De billiga vägarna är ordnade så att varje par av dem slåss om sin egen privata flaskhalsväg, väg A delas av terminal 1 och 2, väg B av terminal 1 och 3, väg C av terminal 2 och 3. I det fraktionerade flödet skickar varje terminal 2/5 av sin efterfrågan billigt och 3/5 dyrt, vilket kostar 30 × 3/5 × 3 = 54. Varje väg bär då 4 + 4 = 8 enheter fraktionerat, och trängselbudgeten är den lasten plus D, alltså 18.

Se nu vad odelbar routing gör med det. Två terminaler som båda går billigt dumpar 10 + 10 = 20 enheter på sin delade väg, över budgeten 18. Så högst en terminal kan rutta billigt; de andra två betalar 30 var. Minsta lagliga odelbara kostnad: 60. Mot en fraktionerad på 54. Det finns åtta routingar, så vi kontrollerar bara alla:

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

Kör det och du får en fraktionerad kostnad på 54, en minsta laglig odelbar kostnad på 60 och ett glapp på 6. De tre överlastade raderna är de tre parvisa konflikterna; de enda routingar som överlever låter högst en terminal gå billigt.

Så förmodan är död? Inte riktigt, och det är den del jag lovade att förklara. Den där uppräkningen med åtta rader säger bara sanningen om varje terminal verkligen har två rutter och inte fler. Bygger du denna graf av faktiska vägar och noder tenderar en fjärde billig rutt att dyka upp ur kombinatoriken. En terminal hittar en tredje väg hem som är billig och håller sig inom budget, och glappet försvinner. Den där extra rutten är precis det fel som modellen rapporterade under sina tre första försök. En ren, symmetrisk mojäng som krossar en 30-årig förmodan i åtta rader Python vore för bra för att vara sant, och det är den också. Koden ovan bevisar att kontrollen är sund och att den eftersträvade egenskapen är verklig. Huruvida en given graf faktiskt har den egenskapen, utan läckor, är den svåra delen, och det är därför Rybins verkliga exempel är en trimmad punkt i en parameterfamilj snarare än en prydlig triangel.

Vad som fortfarande är olöst

Ingen formell artikel har publicerats. Rybin delade konversationen och konstruktionen; ingen av dem har gått igenom den refereeprocess som skulle låta det matematiska samfundet officiellt stänga förmodan.

Den exakt publicerade grafen har inte oberoende återuppbyggts från en primärkälla som jag kan hitta. Siffrorna som cirkulerar kommer från hans inlägg och den delade utskriften. Flera forskare har kontrollerat hans aritmetik och kallat den konsekvent, och en visade att hans exempel ligger inom en oändlig treparametrig familj på samma noder, vilket skulle göra resultatet rikare än en enskild lycklig tillfällighet. Uppmuntrande, men det är informell samhällskontroll, inte en referee-rapport. Behandla 58 kontra 60 som ett väl underbyggt påstående, inte ett fastslaget faktum.

1999 års trängselsats är orörd av allt detta.

Del av ett mönster

Den här historien är inte en enstaka datapunkt. Det är den tredje förmodan som rapporterats falla med AI-assistans på cirka tre månader, och mönstret är värt att dröja vid.

Den 20 juli ska Claude Fable 5 ha hjälpt matematikern Levent Alpöge att hitta ett motexempel till Jacobianska förmodan, ett 87 år gammalt problem. Innan dess, i maj, sades en OpenAI-modell ha motbevisat den 80 år gamla Erdős förmodan om enhetsavstånd. Samma vecka som den här nyheten använde en doktorand vid Columbia GPT-5.6 med ett strukturerat Codex-arbetsflöde för att lösa sex öppna Erdős-problem på fem dagar. Den röda tråden, som en forskare uttryckte det, är att dessa system är bättre på att motbevisa än att bevisa. Ett motexempel är ett enda vittne du kan kontrollera; ett bevis måste täcka varje fall. Den asymmetrin tycks avgöra vilka problem som faller först.

Den praktiska lärdomen är inte "AI löser matematik." Det vi ser är AI som en tålmodig, kombinatoriskt uttömmande sökpartner: en som kan räkna upp parameterfamiljer, hålla felscenarier i arbetsminnet mellan försök och säga sanningen när en konstruktion inte håller. Det är en specifik, användbar förmåga. Och om du vill förstå var den sannolikt slår till härnäst, är frågan att ställa inte vilka förmodanden som är äldst, utan vilka som kan brytas av ett enda kontrollerbart vittne.