GPT-5.6 și conjectura Dinitz–Garg–Goemans

Pe 22 iulie 2026, Dmitry Rybin a postat pe X o afirmație care i-a făcut pe un anumit tip de oameni să lase ceașca de cafea: GPT-5.6 Pro produsese un contraexemplu la conjectura Dinitz–Garg–Goemans, deschisă în optimizarea combinatorie de aproximativ 30 de ani. Dovada de concept era un graf mic. Costul fluxului fracționar 58, costul fluxului nesplittabil 60. Două puncte, trei decenii, patru prompturi.

Majoritatea relatărilor repetă cifrele fără să arate mecanismul din spatele lor, iar acolo e lecția adevărată. Tot acolo trebuie să fiu sincer cu tine despre ce s-a verificat și ce nu. Pe scurt: conceptele sunt solide, noutatea este o afirmație, nu încă un teoremă, iar dacă te așezi să reproduci graful exact de la zero, înțelegi de ce problemele de acest tip sunt grele fix în momentul în care reconstrucția ta începe să "piardă" pe undeva.

Răspunsul rapid

Rybin relatează că GPT-5.6 Pro, ghidat de patru prompturi care însumează sub 60 de cuvinte, a produs un contraexemplu revendicat la conjectura de cost a lui Goemans, o problemă deschisă din aproximativ 1999. Instanța lui este un graf orientat mic, cu o singură sursă și trei terminale de livrare. El afirmă că rutarea splittabilă (fracționară) costă 58, în timp ce orice rutare nesplittabilă care menține congestia în bugetul permis costă cel puțin 60. Acea diferență de două puncte, dacă trece de o verificare formală, este suficientă să scufunde conjectura.

Nu a trecut prin peer review. Rybin a publicat toată conversația din ChatGPT, astfel încât oricine poate citi construcția, iar câteva persoane i-au verificat aritmetica și au găsit-o consecventă. Aritmetica reproductibilă și o demonstrație acceptată sunt însă lucruri diferite, iar distanța dintre ele este toată povestea acestui articol.

Ce este conjectura Dinitz–Garg–Goemans?

Înainte să apreciem ce a căzut, sau ar fi putut să cadă, trebuie să înțelegem ce spune de fapt conjectura.

Imaginează-ți un depozit care expediază comenzi către trei orașe, pe o rețea de drumuri. Dacă ai voie să împarți o expediere, poți trimite jumătate dintr-o comandă pe un drum și jumătate pe altul. Asta e rutare fracționară, și e flexibilă; de obicei găsește un set de rute mai ieftin. Dar multe mărfuri reale nu pot fi împărțite. O comandă, un camion, un drum, de la început la sfârșit. Asta e flux nesplittabil, și asta trebuie să facă, de fapt, o comandă de marfă, un pachet de rețea sau un container.

Întrebarea la care oamenii se gândesc din 1999 e simplă de formulat. Dacă există o rutare splittabilă ieftină, poți găsi întotdeauna o rutare nesplittabilă care să fie tot ieftină, fără să încarce drumurile prea tare?

Yefim Dinitz, Naveen Garg și Michel Goemans au rezolvat jumătate din problemă. Cealaltă jumătate e partea la care a mers GPT-5.6. Ca să înțelegem de ce acea distincție contează enorm, trebuie să fim preciși.

Teorema vs. conjectura

Aceasta e distincția pe care multe relatări o estompează, așa că voi fi precis o dată și apoi mă voi baza pe ea pentru restul articolului.

Dinitz, Garg și Goemans au demonstrat un rezultat despre congestie: dat fiind un flux fracționar valid, îl poți converti întotdeauna într-unul nesplittabil fără să depășești capacitatea vreunui drum cu mai mult decât cea mai mare cerere, numește acea valoare D. Acea teoremă nu e pusă în discuție și n-a fost niciodată.

Ceea ce Goemans a conjecturat separat este versiunea mai puternică, conștientă de cost: că aceeași conversie ar putea ține costul total jos în același timp în care ține jos congestia. Congestie și cost, ambele limitate, într-o singură rutare. Teorema doar despre congestie e în siguranță. Conjectura cost plus congestie e piesa despre care Rybin spune că a căzut. Dacă reții un singur enunț din acest text, lasă-l pe acesta. Multă acoperire entuziastă le încurcă discret pe cele două, iar diferența dintre ele este exact golul matematic care a luat 30 de ani să fie închis.

Ce a construit de fapt GPT-5.6

Instanța lui Rybin e suficient de mică încât să o descrii într-un paragraf. O sursă, câteva noduri intermediare formând o „coloană vertebrală” comună și trei terminale, fiecare cu o cerere. Fiecare terminal are două căi spre casă: o rută directă scumpă sau un ocol gratuit prin coloana comună.

Tensiunea este structurală. Ocoalele ieftine concurează pentru loc pe coloană, așa că, dacă prea multe terminale încearcă să ruteze ieftin deodată, un drum al coloanei se supraîncarcă. Împinge asta suficient de departe și doar un terminal își poate lua calea ieftină în orice rutare nesplittabilă validă. Restul sunt forțate pe rutele directe scumpe, iar costul crește. Fluxul fracționar, liber să se împartă, își împrăștie fiecare cerere pe ambele căi și se strecoară sub fiecare capacitate simultan. Așa obții un cost fracționar sub cel mai mic cost nesplittabil legal. Cifrele lui Rybin pentru instanța lui sunt 58 și 60.

Voi fi sincer cu o limită aici. Nu am reușit să reproduc exact graful lui Rybin, capacitățile specifice și conflictele pereche, dintr-o sursă primară. Transcrierea lui descrie un punct particular într-o familie de parametri, iar descrierea larg răspândită „cu șapte noduri” este o abstractizare a ei, nu o construcție pe care am verificat-o muchie cu muchie. Așa că nu voi prezenta o derivare ordonată a lui 58 și să pretind că e a lui. Ce pot face este să-ți dau o instanță autonomă care arată același mecanism, suficient de mică pentru a fi verificată prin forță brută, ca să vezi cu ochii tăi cum arată „fracționarul bate orice nesplittabil legal”. 

Patru prompturi, câteva ore

Numărul de prompturi e cel mai puțin interesant lucru din această poveste, deși el a devenit viral.

Jurnalul de chat pe care l-a împărtășit Rybin arată că modelul a eșuat la început și a eșuat onest. Promptul de deschidere i-a cerut să găsească un contraexemplu structurat. A lucrat mai bine de o oră și s-a întors cu mâna goală, spunând direct că a prezenta ce are drept un contraexemplu valid ar fi fals.

Pus să continue, a rulat din nou și iar n-a raportat nimic, descriind cum fiecare construcție promițătoare tot făcea să apară o rută suplimentară ascunsă care distrugea separarea cost–congestie odată ce toate căile erau enumerate. Un al treilea prompt care cerea o strategie mai curată a obținut un cadru mai îngust și tot fără rezultat final.

Asta nu e „patru prompturi și gata”. Sunt ore în care un model lovește ziduri și spune adevărul despre ele. Zidul specific în care tot lovea — apare o rută în plus și strică separarea — este exact ce a fost construită să prevină construcția finală, prin fixarea fiecărui terminal la exact două căi, astfel încât întreg spațiul de rutare să fie opt opțiuni pe care le poți enumera de mână. Ține minte acest mod de eșec. Urmează să dai tu însuți peste el.

Al patrulea prompt, relatat ca fiind ceva de genul „m-am săturat de eșecul tău, te rog termină cu un contraexemplu complet, necondiționat”, este cel care a produs construcția funcțională, împreună cu certificate de dovadă, un program de enumerare și LaTeX complet. Răbdarea a contat. La fel și refuzurile anterioare; au fost autoevaluări oneste.

Verifică singur

Aici acoperirea DataCamp poate face ceva ce un articol de știri nu poate: te lasă să rulezi verificarea.

Un avertisment rapid înainte de cod. Ce urmează nu este graful lui Rybin. E o instanță schematică pe care am construit-o cinstit, una în care fiecare terminal are într-adevăr exact două rute, aritmetica se închide, iar diferența este reală. Îți arată forma unui astfel de contraexemplu și tehnica de verificare. Nu, de una singură, nu infirmă nimic, și voi explica de ce imediat după ce o rulezi.

Configurația: trei terminale, fiecare expediază 10 unități, deci cea mai mare cerere D este 10. Fiecare are o cale directă scumpă (cost 30) și o cale ieftină gratuită. Căile ieftine sunt aranjate astfel încât fiecare pereche dintre ele să se lupte pentru propriul lor drum cu gât de sticlă, drumul A e partajat de terminalele 1 și 2, drumul B de 1 și 3, drumul C de 2 și 3. În fluxul fracționar, fiecare terminal trimite 2/5 din cerere pe ieftin și 3/5 pe scump, ceea ce costă 30 x 3/5 x 3 = 54. Fiecare drum poartă apoi fracționar 4 + 4 = 8 unități, iar bugetul de congestie este acea încărcare plus D, deci 18.

Acum vezi ce face rutarea nesplittabilă cu asta. Două terminale care aleg ieftin descarcă 10 + 10 = 20 de unități pe drumul lor comun, peste bugetul de 18. Așadar, cel mult un terminal poate rutezi ieftin; celelalte două plătesc câte 30. Costul minim legal nesplittabil: 60. Comparativ cu 54 fracționar. Există opt rutări, deci le verificăm pe toate:

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

Rulează și obții un cost fracționar de 54, un cost minim legal nesplittabil de 60 și o diferență de 6. Cele trei rânduri supraîncărcate sunt cele trei conflicte perechi; singurele rutări care supraviețuiesc țin cel mult un terminal pe ieftin.

Deci conjectura e moartă? Nu chiar, și asta e partea pe care am promis să o explic. Acea enumerare în opt rânduri spune adevărul doar dacă fiecare terminal are într-adevăr două rute și niciuna în plus. Construiește acest graf din drumuri și noduri reale și tinde să apară o a patra rută ieftină din combinatorică. Un terminal găsește o a treia cale spre casă care e ieftină și rămâne în buget, iar diferența dispare. Acea rută în plus e exact eșecul pe care modelul l-a raportat în primele trei încercări. Un „gadget” curat, simetric, care sparge o conjectură de 30 de ani în opt linii de Python ar fi prea frumos ca să fie adevărat — și chiar e. Codul de mai sus demonstrează că verificarea e solidă și proprietatea-țintă este reală. Dacă un graf anume chiar are acea proprietate, fără „scurgeri”, e partea grea, și de aceea instanța reală a lui Rybin e un punct ajustat într-o familie de parametri, nu un triunghi ordonat.

Ce rămâne nerezolvat

Nu a apărut nicio lucrare formală. Rybin a împărtășit conversația și construcția; niciuna nu a trecut prin procesul de referențiere care ar permite comunității matematice să închidă oficial conjectura.

Graful publicat exact nu a fost reconstruit independent dintr-o sursă primară pe care să o pot găsi. Numerele care circulă vin din postarea lui și transcrierea partajată. Câțiva cercetători i-au verificat aritmetica și au numit-o consecventă, iar unul a arătat că instanța lui se află într-o familie infinită cu trei parametri pe aceleași noduri, ceea ce ar face rezultatul mai bogat decât o simplă coincidență norocoasă. Încurajator, dar asta e verificare informală a comunității, nu un raport de referent. Tratează diferența 58 vs. 60 ca pe o afirmație bine susținută, nu ca pe un fapt stabilit.

Teorema despre congestie din 1999 nu e atinsă de nimic din toate acestea.

Parte dintr-un tipar

Această poveste nu e un singur punct de date. E a treia conjectură despre care se relatează că a căzut cu asistență AI în vreo trei luni, iar tiparul merită analizat.

Pe 20 iulie, Claude Fable 5 ar fi ajutat matematicianul Levent Alpöge să găsească un contraexemplu la conjectura Jacobiană, o problemă veche de 87 de ani. Înainte de asta, în mai, se spunea că un model OpenAI a infirmat conjectura Erdős a distanței unitare, veche de 80 de ani. În aceeași săptămână cu această știre, un doctorand de la Columbia a folosit GPT-5.6 cu un flux de lucru Codex structurat pentru a rezolva șase probleme deschise ale lui Erdős în cinci zile. Ideea comună, cum a spus un cercetător, e că aceste sisteme sunt mai bune la a infirma decât la a demonstra. Un contraexemplu este un singur martor pe care îl poți verifica; o demonstrație trebuie să acopere fiecare caz. Acea asimetrie pare să decidă ce probleme cad primele.

Concluzia practică nu e „AI rezolvă matematica”. Ceea ce vedem este AI lucrând ca un partener de căutare răbdător, combinatoric, exhaustiv: unul care poate enumera familii de parametri, poate ține moduri de eșec în memoria de lucru peste încercări și poate spune adevărul când o construcție nu se închide. E o capabilitate specifică, utilă. Și dacă vrei să înțelegi unde ar putea lovi data viitoare, întrebarea de pus nu e care conjecturi sunt cele mai vechi, ci care pot fi sparte de un singur martor verificabil.