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 jos: GPT-5.6 Pro ar fi produs un contraexemplu la conjectura Dinitz–Garg–Goemans, deschisă în optimizarea combinatorică de aproximativ 30 de ani. Dovada de concept era un mic graf. Costul fluxului fracționar 58, costul fluxului indivizibil 60. Două puncte, trei decenii, patru prompturi.

Majoritatea relatărilor repetă cifrele fără să arate mecanismul din spatele lor, iar tocmai în mecanism stă adevărata lecție. Tot acolo trebuie să fiu sincer cu tine privind ce a fost verificat și ce nu. Pe scurt: conceptele sunt solide, vestea este o afirmație și încă nu un teoremă, iar dacă te apuci să refaci de la zero graful exact, înțelegi de ce problemele de acest tip sunt grele în clipa în care reconstrucția ta începe să „curgă”.

Răspunsul pe scurt

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

Nu a trecut prin peer review. Rybin a publicat întreaga conversație din ChatGPT pentru ca oricine să poată citi construcția, iar mai multe persoane i-au verificat aritmetica și au găsit-o consecventă. Aritmetica reproductibilă și o demonstrație acceptată sunt însă animale diferite, iar distanța dintre ele e toată povestea acestui articol.

Ce este conjectura Dinitz–Garg–Goemans?

Înainte să apreciem ce a căzut, sau ar putea să fi căzut, 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 rutieră. 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 mai ieftin de rute. 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 indivizibil și e ceea ce un ordin de marfă, un pachet de rețea sau un container chiar trebuie să facă.

Întrebarea la care oamenii rumegă din 1999 e simplu de formulat. Dacă există o rutare splittabilă ieftină, poți găsi întotdeauna o rutare indivizibilă care să fie de asemenea ieftină fără să supraîncarci prea tare drumurile?

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

Teorema vs. conjectura

Asta e distincția pe care majoritatea textelor o estompează, așa că voi fi precis o dată, apoi voi conta pe ea pentru restul articolului.

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

Ceea ce Goemans a conjecturat separat este versiunea mai puternică, conștientă de cost: că aceeași conversie ar putea menține costul total jos în același timp în care ține congestia jos. Congestie și cost, ambele limitate, într-o singură rutare. Teorema doar cu congestia e în siguranță. Conjectura cost-plus-congestie e piesa despre care Rybin spune că a căzut. Dacă rămâi cu o singură propoziție din acest text, să fie aceasta. Multă acoperire entuziastă le schimbă tacit, iar diferența dintre ele e 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ă pentru a fi descrisă într-un paragraf. O sursă, câteva noduri intermediare care formează 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 e structurală. Ocoalele ieftine concurează pentru loc pe coloană, așa că dacă prea multe terminale încearcă să ruteze ieftin deodată, un drum din coloană se supraîncarcă. Împinge asta suficient de departe și doar un terminal poate lua calea ieftină într-o rutare indivizibilă validă. Restul sunt forțate pe căile lor directe scumpe, iar costul urcă. Fluxul fracționar, liber să se împartă, își împrăștie fiecare cerere pe ambele căi și se strecoară sub fiecare capacitate deodată. Așa obții un cost fracționar sub cel mai ieftin cost indivizibil 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 graful exact al lui Rybin, capacitățile specifice și conflictele pereche, dintr-o sursă primară. Transcrierea lui descrie un anumit punct într-o familie de parametri, iar descrierea răspândită „cu șapte noduri” e o abstractizare a ei, nu o construcție pe care am verificat-o muchie cu muchie. Așa că nu o să pun în scenă o deducție 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 indivizibil legal”. 

Patru prompturi, câteva ore

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

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

Pus să continue, a rulat din nou și iar a raportat nimic, descriind cum fiecare construcție promițătoare tot scotea la iveală o opțiune suplimentară de rutare ascunsă care distrugea separarea cost-congestie odată enumerate toate căile. Un al treilea prompt care cerea o strategie mai curată a adus un cadru mai îngust și tot niciun rezultat final.

Asta nu e „patru prompturi și gata”. Sunt ore întregi în care un model lovește ziduri și spune adevărul despre ele. Zidul specific în care tot dădea, apare o rută în plus și ruinează separarea, este exact ceea ce construcția finală a fost concepută să prevină, prin fixarea fiecărui terminal la exact două căi astfel încât întregul spațiu de rutare să fie opt opțiuni pe care le poți enumera manual. Ține minte acest mod de eșec. Ești pe cale să dai de el tu însuți.

Al patrulea prompt, relatat ca fiind ceva apropiat de „m-am săturat de eșecurile tale, te rog termină cu un contraexemplu complet și necondiționat”, este cel care a produs construcția funcțională, împreună cu certificate de verificare, 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 o știre nu poate: îți permite să rulezi verificarea.

Un scurt avertisment înainte de cod. Ce urmează nu este graful lui Rybin. E o instanță schematică pe care am construit-o ca să fie onestă, una în care fiecare terminal are exact două rute, aritmetica se închide și diferența e reală. Îți arată forma unui astfel de contraexemplu și tehnica de verificare. De una singură, nu infirmă nimic, iar imediat după ce o rulezi îți explic de ce.

Configurația: trei terminale, fiecare expediind 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 se luptă pentru propriul drum-gât-de-sticlă privat, drumul A e împărțit 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 4 + 4 = 8 unități fracționar, iar bugetul de congestie este acea încărcare plus D, deci 18.

Acum vezi ce face rutarea indivizibilă cu asta. Două terminale care merg ambele pe ieftin aruncă 10 + 10 = 20 de unități pe drumul lor comun, peste bugetul de 18. Deci cel mult un terminal poate ruteze ieftin; celelalte două plătesc câte 30. Costul minim indivizibil legal: 60. Versus un fracționar de 54. Există opt rutări, așa că 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ă-l și obții un cost fracționar de 54, un cost minim indivizibil legal 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 menț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 nu mai multe. 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 se închide. Acea rută în plus este exact eșecul pe care modelul l-a raportat în primele trei încercări. Un „gadget” curat, simetric, care dărâmă o conjectură veche de 30 de ani în opt rânduri de Python ar fi prea frumos ca să fie adevărat, și chiar este. Codul de mai sus demonstrează că verificarea e solidă și proprietatea-țintă e reală. Dacă un anumit graf are de fapt acea proprietate, fără scurgeri, asta 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 din transcrierea distribuită. 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 singură coincidență norocoasă. Încurajator, dar asta e verificare informală din comunitate, nu un raport de referenți. Tratează diferența 58 vs 60 ca o afirmație bine susținută, nu ca un fapt stabilit.

Teorema despre congestie din 1999 rămâne neatinsă de toate acestea.

Parte dintr-un tipar

Această poveste nu e un singur punct de date. Este a treia conjectură despre care se raportează că a căzut cu asistență AI în aproximativ 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 spune că un model OpenAI ar fi infirmat conjectura lui Erdős despre distanță unitară, veche de 80 de ani. În aceeași săptămână cu această veste, 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. Firul comun, cum a spus un cercetător, este 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 este „AI rezolvă matematica”. Ceea ce vedem este AI lucrând ca un partener de căutare răbdător, exhaustiv din punct de vedere combinatoric: unul care poate enumera familii de parametri, poate păstra modurile de eșec în memoria de lucru de-a lungul încercărilor și poate spune adevărul când o construcție nu se închide. E o capabilitate specifică și utilă. Iar dacă vrei să înțelegi unde va lovi probabil data viitoare, întrebarea de pus nu e care conjecturi sunt cele mai vechi, ci care pot fi sparte de un singur martor verificabil.