GPT-5.6 och Dinitz–Garg–Goemans-konjekturet

Den 22 juli 2026 publicerade Dmitry Rybin ett påstående på X som fick en viss sorts person att lägga ifrån sig kaffet: GPT-5.6 Pro hade tagit fram ett motexempel till Dinitz–Garg–Goemans-konjekturet, som varit öppet inom kombinatorisk optimering i cirka 30 år. Bevisidén var en liten graf. Fraktionerad flödeskostnad 58, osplitbar flödeskostnad 60. Två poäng, tre decennier, fyra promptar.

De flesta beskrivningar upprepar siffrorna utan att visa mekanismen bakom, och det är i mekanismen den riktiga lärdomen finns. Det är också där jag måste vara rak med vad som har verifierats och vad som inte har det. Kortversion: begreppen är solida, nyheten är ett anspråk och ännu inte en 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 promptar på totalt under 60 ord, tog fram ett påstått motexempel till Goemans kostnadskonjektur, ett problem som varit öppet sedan ungefär 1999. Hans exempel är en liten riktad graf med en enda källa och tre terminaler för leverans. Han anger att den splittbara (fraktionerade) routingen kostar 58, medan varje osplitbar routing som håller trängseln inom den tillåtna budgeten kostar minst 60. Den tvåpoängsglappet, om det överlever formell granskning, räcker för att sänka konjekturet.

Det har inte genomgått peer review. Rybin publicerade hela ChatGPT-samtalet så att alla kan läsa konstruktionen, och flera 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 poängen med den här artikeln.

Vad är Dinitz–Garg–Goemans-konjekturet?

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

Föreställ dig ett lager som skickar beställningar till tre städer via ett vägnät. Om du får dela upp en sändning kan du skicka halva beställningen på en väg och halva på en annan. Det är fraktionerad routing, och den är flexibel; den hittar vanligtvis en billigare uppsättning vägar. Men mycket verklig frakt kan inte delas. En beställning, en lastbil, en väg, från början till slut. Det är osplitbart flöde, och det är vad en fraktorder, ett nätverkspaket eller en container faktiskt måste göra.

Frågan man har brottats med sedan 1999 är enkel att formulera. Om en billig splittbar routing finns, kan du alltid hitta en osplitbar routing som också är billig utan att överbelasta vägarna alltför mycket?

Yefim Dinitz, Naveen Garg och Michel Goemans löste halva problemet. Den andra halvan är den del 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 konjekturet

Detta är skillnaden de flesta texter suddar ut, så jag är tydlig en gång och förlitar mig sedan på det i resten av artikeln.

Dinitz, Garg och Goemans bevisade ett resultat om trängsel: givet ett giltigt fraktionerat flöde kan du alltid konvertera det till ett osplitbart utan att överskrida någon vägs kapacitet med mer än den enskilt största efterfrågan, kalla den siffran D. Den satsen ifrågasätts inte och har aldrig gjort det.

Vad Goemans separat konjicerade är den starkare, kostnadsmedvetna versionen: att samma konvertering samtidigt kan hålla nere den totala kostnaden när den håller nere trängseln. Trängsel och kostnad, båda begränsade, i en och samma routing. Satsen om endast trängsel är säker. Konjekturet om kostnad plus trängsel är den del som Rybin säger föll. Om du ska ta med dig en mening från den här texten, låt det vara den. Mycket av den upphetsade rapporteringen byter tyst plats på de två, och skillnaden mellan dem är hela det matematiska gapet 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 mellanliggande noder som bildar en gemensam ”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 via den gemensamma ryggraden.

Spänningen är strukturell. De billiga omvägarna konkurrerar om utrymme på ryggraden, så om för många terminaler försöker rutta billigt samtidigt svämmar en ryggradsväg över. Pressa det tillräckligt långt och endast en terminal kan ta sin billiga väg i någon giltig osplitbar routing. Resten tvingas ut på sina dyra direktvägar, och kostnaden stiger. Det fraktionerade flödet, fritt att delas, sprider varje efterfrågan över båda vägarna och tar sig under varje kapacitet samtidigt. Det är så du får en fraktionerad kostnad under den billigaste lagliga osplitbara 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 transkript beskriver en särskild punkt i en parameterfamilj, och den allmänt spridda ”sjunods”-beskrivningen ä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älvständigt 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 osplitbar” ser ut. 

Fyra promptar, flera timmar

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

Chatloggen Rybin delade visar att modellen först misslyckades, och misslyckades ärligt. Den inledande prompten bad den hitta ett strukturerat motexempel. Den arbetade i drygt en timme och kom tillbaka tomhänt, och sade rent ut att det vore falskt att presentera det den hade som ett giltigt motexempel.

Uppmanad att fortsätta körde den igen, och rapporterade återigen ingenting, 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 prompt som bad om en renare strategi gav ett snävare ramverk men fortfarande inget färdigt resultat.

Det där är inte ”fyra promptar, 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 slog i, en extra rutt dyker upp och förstör separationen, är exakt det som 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 lista för hand. Ha den felmekanismen i åtanke. Du är på väg att stöta på den själv.

Den fjärde prompten, uppges vara något i stil med "nu räcker det med dina misslyckanden, 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ägran; de var ärliga självbedömningar.

Kontrollera själv

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

En snabb brasklapp innan koden. Det som följer är inte Rybins graf. Det är ett schematiskt exempel jag byggt för att vara ärligt, där varje terminal verkligen har exakt två rutter, aritmetiken går ihop och gapet är verkligt. Det visar formen av ett sådant motexempel och tekniken för att kontrollera ett. Det motbevisar inte något i sig självt, 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 osplitbar routing gör med det. Två terminaler som båda går billigt lägger 10 + 10 = 20 enheter på sin gemensamma väg, över budgeten 18. Så högst en terminal kan rutta billigt; de andra två betalar 30 var. Minsta lagliga osplitbara kostnad: 60. Mot en fraktionerad på 54. Åtta routingar finns, 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 du det får du en fraktionerad kostnad på 54, en minsta laglig osplitbar kostnad på 60 och ett gap på 6. De tre överbelastade raderna är de tre parvisa konflikterna; de enda routingar som överlever håller högst en terminal billig.

Så konjekturet är dött? 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 den här grafen 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 gapet stängs. Den extra rutten är exakt det fel som modellen rapporterade under sina tre första försök. En ren, symmetrisk mojäng som krossar ett 30-årigt konjektur i åtta rader Python vore för bra för att vara sant, och det är det. Koden ovan visar att kontrollen är sund och att mål-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 avstämd punkt i en parameterfamilj snarare än en prydlig triangel.

Vad som fortfarande är oklart

Ingen formell artikel har publicerats. Rybin delade samtalet och konstruktionen; inget av dem har genomgått granskningsprocessen som skulle låta det matematiska samfundet officiellt stänga konjekturet.

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 det delade transkriptet. Flera forskare har kontrollerat hans aritmetik och kallat den konsekvent, och en visade att hans exempel ligger inom en oändlig tre-parameterfamilj på samma noder, vilket skulle göra resultatet rikare än en enstaka lyckosam slump. Uppmuntrande, men det är informell granskning i communityn, inte en referee-rapport. Behandla 58‑vs‑60 som ett välunderstött anspråk, inte ett fastslaget faktum.

1999 års sats om trängsel berörs inte av något av detta.

Del av ett mönster

Det här är inte en enstaka datapunkt. Det är den tredje konjekturen som rapporterats falla med AI-assistans på ungefär 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 Jacobikonjekturet, ett 87 år gammalt problem. Innan dess, i maj, sades en OpenAI-modell ha motbevisat det 80 år gamla Erdős enhetsavståndskonjekturet. 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 alla fall. Den asymmetrin verkar avgöra vilka problem som faller först.

Den praktiska slutsatsen ä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 felmekanismer i arbetsminnet över flera försök och tala sanning när en konstruktion inte håller ihop. 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 inte vilka konjektur som är äldst, utan vilka som kan krossas av ett enda kontrollerbart vittne.