GPT-5.6 e la congettura di Dinitz-Garg-Goemans

Il 22 luglio 2026, Dmitry Rybin ha pubblicato su X un'affermazione che ha fatto posare il caffè a più di qualcuno: GPT-5.6 Pro aveva prodotto un controesempio alla congettura di Dinitz-Garg-Goemans, aperta nell'ottimizzazione combinatoria da circa 30 anni. La prova di concetto era un piccolo grafo. Costo del flusso frazionario 58, costo del flusso non scindibile 60. Due punti, tre decenni, quattro prompt.

La maggior parte delle cronache ripete i numeri senza mostrare il meccanismo che li genera, ed è proprio lì che sta la lezione vera. È anche il punto in cui devo essere chiaro su cosa è stato verificato e cosa no. In breve: i concetti sono solidi, la notizia è una rivendicazione e non ancora un teorema, e se ti metti a ricostruire da zero il grafo esatto, capisci perché problemi come questo sono difficili nel momento stesso in cui la tua ricostruzione fa acqua.

La risposta breve

Rybin riferisce che GPT-5.6 Pro, guidato da quattro prompt per meno di 60 parole in totale, ha prodotto un presunto controesempio alla congettura sui costi di Goemans, un problema aperto più o meno dal 1999. Il suo caso è un piccolo grafo orientato con un'unica sorgente e tre terminal di consegna. Afferma che l'instradamento scindibile (frazionario) costa 58, mentre qualunque instradamento non scindibile che mantenga la congestione entro il budget consentito costa almeno 60. Quel divario di due punti, se supererà la revisione formale, basta ad affondare la congettura.

Non è passato attraverso peer review. Rybin ha pubblicato l’intera conversazione con ChatGPT così che chiunque possa leggere la costruzione, e diverse persone hanno controllato la sua aritmetica trovandola coerente. Aritmetica riproducibile e una dimostrazione accettata, però, sono cose diverse, e la distanza tra le due è tutta la storia di questo articolo.

Che cos’è la congettura di Dinitz-Garg-Goemans?

Prima di apprezzare cosa è caduto, o potrebbe esserlo, dobbiamo capire cosa dice davvero la congettura.

Immagina un magazzino che spedisce ordini a tre città lungo una rete stradale. Se ti è permesso scindere una spedizione, puoi mandare metà ordine per una strada e metà per un’altra. Questo è l’instradamento frazionario, ed è flessibile; di solito trova un insieme di percorsi più economico. Ma molte merci reali non possono essere scisse. Un ordine, un camion, una strada, dall’inizio alla fine. Questo è il flusso non scindibile, ed è ciò che un ordine di trasporto, un pacchetto di rete o un container devono effettivamente fare.

La domanda su cui le persone si interrogano dal 1999 è semplice da dichiarare. Se esiste un instradamento scindibile economico, puoi sempre trovare un instradamento non scindibile che sia anche economico senza sovraccaricare troppo le strade?

Yefim Dinitz, Naveen Garg e Michel Goemans ne hanno risolta metà. L’altra metà è quella su cui è andato a segno GPT-5.6. Per capire perché quella distinzione conta tantissimo, dobbiamo essere precisi.

Il teorema vs la congettura

È la distinzione che la maggior parte degli articoli sfuma, quindi sarò preciso una volta sola e poi ci farò affidamento per il resto del pezzo.

Dinitz, Garg e Goemans hanno dimostrato un risultato sulla congestione: dato un flusso frazionario valido, puoi sempre convertirlo in uno non scindibile senza superare la capacità di nessuna strada di più della massima domanda singola, chiamiamo quel numero D. Quel teorema non è in discussione e non lo è mai stato.

Quello che Goemans separatamente ha congetturato è la versione più forte e attenta ai costi: che la stessa conversione potesse tenere basso il costo totale nello stesso momento in cui tiene bassa la congestione. Congestione e costo, entrambi limitati, in un unico instradamento. Il teorema solo-congestione è al sicuro. La congettura costo+congestione è il pezzo che, secondo Rybin, è caduto. Se devi ricordare una sola frase di questo pezzo, che sia questa. Molte cronache entusiaste scambiano sottovoce le due cose, e la differenza tra loro è l’intero divario matematico che ha richiesto 30 anni per chiudersi.

Cosa ha costruito davvero GPT-5.6

Il caso di Rybin è abbastanza piccolo da poter essere descritto in un paragrafo. Una sorgente, alcuni nodi intermedi che formano una “spina” condivisa, e tre terminal, ciascuno con una domanda. Ogni terminal ha due vie per tornare a casa: un percorso diretto costoso, oppure una deviazione gratuita attraverso la spina condivisa.

La tensione è strutturale. Le deviazioni economiche competono per lo spazio sulla spina, quindi se troppi terminal provano a instradare al risparmio contemporaneamente, una strada della spina va in overflow. Spingendo abbastanza quel meccanismo, in qualunque instradamento non scindibile valido solo un terminal può prendere il suo percorso economico. Gli altri sono costretti sui percorsi diretti costosi e il costo sale. Il flusso frazionario, libero di scindersi, distribuisce ciascuna domanda su entrambi i percorsi e rientra sotto ogni capacità contemporaneamente. È così che ottieni un costo frazionario inferiore al costo non scindibile legale più economico. Le cifre di Rybin per il suo caso sono 58 e 60.

Sarò onesto su un limite qui. Non sono riuscito a riprodurre il grafo esatto di Rybin, le capacità specifiche e i conflitti a coppie, da una fonte primaria. La sua trascrizione descrive un punto particolare in una famiglia di parametri, e la diffusa descrizione “a sette nodi” è un’astrazione di essa, non una costruzione che ho verificato arco per arco. Quindi non metterò in scena una derivazione ordinata di 58 facendo finta che sia la sua. Quello che posso fare è consegnarti un caso autosufficiente che mostra lo stesso meccanismo, abbastanza piccolo da poter essere controllato per forza bruta, così puoi vedere con i tuoi occhi cosa significa “il frazionario batte ogni non scindibile legale”. 

Quattro prompt, diverse ore

Il numero di prompt è la cosa meno interessante di questa storia, anche se è la parte che è diventata virale.

Il registro della chat condiviso da Rybin mostra che il modello ha fallito all’inizio, e ha fallito con accuratezza. Il prompt iniziale gli chiedeva di trovare un controesempio strutturato. Ha lavorato per buona parte di un’ora ed è tornato a mani vuote, dichiarando esplicitamente che presentare quanto aveva come un controesempio valido sarebbe stato falso.

Invitato a proseguire, ha eseguito di nuovo, e di nuovo non ha riportato nulla, descrivendo come ogni costruzione promettente finisse per far spuntare un’opzione di instradamento extra nascosta che distruggeva la separazione costi-congestione una volta enumerati tutti i percorsi. Un terzo prompt che chiedeva una strategia più pulita ha ottenuto un quadro più ristretto e ancora nessun risultato conclusivo.

Questo non è “quattro prompt e via”. Sono ore di un modello che sbatte contro muri e dice la verità al riguardo. Il muro specifico contro cui continuava a sbattere — appare un percorso extra e rovina la separazione — è esattamente ciò che la costruzione finale è stata progettata per impedire, vincolando ciascun terminal a esattamente due percorsi così che l’intero spazio degli instradamenti sia di otto opzioni enumerabili a mano. Tieni a mente quella modalità di fallimento. Stai per imbatterti in essa tu stesso.

Il quarto prompt, a quanto pare qualcosa di vicino a "ne ho abbastanza dei tuoi fallimenti, per favore finisci con un controesempio completo e incondizionato," è quello che ha prodotto la costruzione funzionante, insieme a certificati di prova, un programma di enumerazione e il LaTeX completo. La pazienza è stata importante. Lo sono state anche le precedenti rinunce; erano autovalutazioni oneste.

Verificalo tu stesso

Qui la copertura di DataCamp può fare qualcosa che un post di cronaca non può: lasciarti eseguire la verifica.

Un rapido caveat prima del codice. Quello che segue non è il grafo di Rybin. È un caso schematico che ho costruito per essere onesto, in cui ogni terminal ha davvero esattamente due percorsi, l’aritmetica torna e il divario è reale. Ti mostra la forma di un tale controesempio e la tecnica per verificarlo. Da solo, non smentisce nulla, e ti spiegherò perché subito dopo che lo esegui.

L’impostazione: tre terminal, ciascuno spedisce 10 unità, quindi la domanda massima D è 10. Ognuno ha un percorso diretto costoso (costo 30) e un percorso economico gratuito. I percorsi economici sono disposti in modo che ogni coppia di essi si contenda il proprio collo di bottiglia privato: la strada A è condivisa dai terminal 1 e 2, la strada B dai terminal 1 e 3, la strada C dai terminal 2 e 3. Nel flusso frazionario, ciascun terminal invia 2/5 della sua domanda per la via economica e 3/5 per la via costosa, per un costo di 30 x 3/5 x 3 = 54. Ogni strada trasporta quindi 4 + 4 = 8 unità in modo frazionario, e il budget di congestione è quel carico più D, quindi 18.

Ora guarda cosa fa l’instradamento non scindibile. Due terminal che vanno entrambi al risparmio scaricano 10 + 10 = 20 unità sulla loro strada condivisa, oltre il budget di 18. Quindi al massimo un terminal può instradare al risparmio; gli altri due pagano 30 ciascuno. Costo minimo non scindibile legale: 60. Contro un frazionario di 54. Esistono otto instradamenti, quindi li controlliamo tutti:

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

Eseguilo e ottieni un costo frazionario di 54, un costo minimo non scindibile legale di 60 e un divario di 6. Le tre righe in overload sono i tre conflitti a coppie; gli unici instradamenti che sopravvivono mantengono al massimo un terminal al risparmio.

Quindi la congettura è morta? Non proprio, ed è la parte che avevo promesso di spiegare. Quell’enumerazione a otto righe dice la verità solo se ogni terminal ha davvero due percorsi e non di più. Costruisci questo grafo con strade e nodi reali, e tende a comparire un quarto percorso economico dalla combinatoria. Un terminal trova una terza via di casa che è economica e resta sotto budget, e il divario si chiude. Quel percorso extra è l’esatto fallimento che il modello ha riportato nei primi tre tentativi. Un gadget pulito e simmetrico che infrange una congettura trentennale in otto righe di Python sarebbe troppo bello per essere vero, e infatti lo è. Il codice sopra dimostra che il controllo è corretto e che la proprietà da verificare è reale. Se un dato grafo abbia effettivamente quella proprietà, senza perdite, è la parte difficile, ed è il motivo per cui il caso reale di Rybin è un punto tarato in una famiglia di parametri piuttosto che un triangolo ordinato.

Cosa resta irrisolto

Non è apparso alcun paper formale. Rybin ha condiviso la conversazione e la costruzione; nessuna delle due è passata attraverso il processo di referaggio che permetterebbe alla comunità matematica di chiudere ufficialmente la congettura.

Il grafo pubblicato esatto non è stato ricostruito in modo indipendente da una fonte primaria che io riesca a trovare. I numeri in circolazione provengono dal suo post e dalla trascrizione condivisa. Diversi ricercatori hanno controllato la sua aritmetica e l’hanno definita coerente, e uno ha mostrato che il suo caso si colloca all’interno di una famiglia infinita a tre parametri sugli stessi nodi, il che renderebbe il risultato più ricco di una singola fortunata coincidenza. Incoraggiante, ma si tratta di controlli informali da parte della comunità, non di una relazione di referaggio. Considera il 58 contro 60 come un’affermazione ben supportata, non come un fatto assodato.

Il teorema sulla congestione del 1999 non è toccato da nulla di tutto questo.

Parte di un pattern

Questa storia non è un singolo dato. È la terza congettura che si dice sia caduta con assistenza AI in circa tre mesi, e vale la pena riflettere sul pattern.

Il 20 luglio, si dice che Claude Fable 5 abbia aiutato il matematico Levent Alpöge a trovare un controesempio alla congettura di Jacobian, un problema vecchio di 87 anni. Prima ancora, a maggio, si dice che un modello OpenAI abbia smentito la congettura delle distanze unitarie di Erdős, vecchia di 80 anni. Nella stessa settimana di questa notizia, uno studente di dottorato della Columbia ha usato GPT-5.6 con un workflow Codex strutturato per risolvere sei problemi aperti di Erdős in cinque giorni. Il filo conduttore, come ha detto un ricercatore, è che questi sistemi sono più bravi a smentire che a dimostrare. Un controesempio è un singolo testimone che puoi verificare; una dimostrazione deve coprire ogni caso. Questa asimmetria sembra decidere quali problemi cadono per primi.

La lezione pratica non è “l’AI risolve la matematica”. Quello che stiamo vedendo è l’AI che lavora come un paziente partner di ricerca esaustivo dal punto di vista combinatorio: uno che può enumerare famiglie di parametri, mantenere le modalità di fallimento in memoria di lavoro tra i tentativi e dire la verità quando una costruzione non si chiude. È una capacità specifica e utile. E se vuoi capire dove colpirà probabilmente la prossima volta, la domanda da porsi non è quali congetture sono più antiche, ma quali possono essere infrante da un singolo testimone verificabile.