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 la tazzina 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 frazionabile 60. Due punti, tre decenni, quattro prompt.

La maggior parte degli articoli ripete i numeri senza mostrare il meccanismo che li genera, ed è proprio lì che sta la vera lezione. È anche il punto in cui devo essere chiaro su cosa sia stato verificato e cosa no. Versione breve: i concetti sono solidi, la notizia è un'affermazione e non ancora un teorema, e se ti metti a ricostruire da zero il grafo esatto, capirai subito perché problemi così sono difficili, nel momento 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 sul costo di Goemans, un problema aperto dal 1999 circa. Il suo caso è un piccolo grafo diretto con un’unica sorgente e tre terminal di consegna. Afferma che l’instradamento frazionabile (splittable) costa 58, mentre qualsiasi instradamento non frazionabile 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 per la peer review. Rybin ha pubblicato l’intera conversazione con ChatGPT così che chiunque possa leggerne la costruzione, e diverse persone hanno controllato la sua aritmetica, trovandola coerente. Aritmetica riproducibile e dimostrazione accettata sono però cose diverse, e la distanza tra le due è l’intera storia di questo articolo.

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

Prima di apprezzare cosa sia caduto, o potrebbe esserlo, serve capire cosa dica davvero la congettura.

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

La domanda su cui si ragiona dal 1999 è semplice da enunciare. Se esiste un instradamento frazionabile economico, puoi sempre trovare un instradamento non frazionabile che sia anch’esso economico senza sovraccaricare troppo le strade?

Yefim Dinitz, Naveen Garg e Michel Goemans ne hanno risolta metà. L’altra metà è quella su cui si è lanciato GPT-5.6. Per capire perché questa distinzione conti enormemente, dobbiamo essere precisi.

Il teorema vs la congettura

È la distinzione che la maggior parte dei resoconti sfuma; quindi sarò preciso una volta e poi ci farò affidamento per il resto dell’articolo.

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

Quello che Goemans ha congetturato separatamente è la versione più forte e attenta ai costi: che la stessa conversione possa mantenere basso il costo totale mentre tiene bassa la congestione. Congestione e costo, entrambi limitati, in un unico instradamento. Il teorema sulla sola congestione è al sicuro. La congettura costo+congestione è il pezzo che, secondo Rybin, sarebbe caduto. Se devi portarti via una sola frase, che sia questa. Molta della copertura entusiastica scambia silenziosamente le due, e la differenza tra esse è proprio il divario matematico che ha richiesto 30 anni per essere colmato.

Cosa ha costruito davvero GPT-5.6

L’istanza di Rybin è abbastanza piccola da descriversi in un paragrafo. Una sorgente, alcuni nodi intermedi che formano una "spina dorsale" condivisa, e tre terminal, ciascuno con una domanda. Ogni terminal ha due strade di casa: un percorso diretto costoso oppure una deviazione gratuita attraverso la spina condivisa.

La tensione è strutturale. Le deviazioni economiche competono per spazio sulla spina, quindi se troppi terminal provano a instradare al risparmio contemporaneamente, una strada della spina trabocca. Spingendo abbastanza, in qualsiasi instradamento non frazionabile valido solo un terminal può prendere la sua via economica. Gli altri sono costretti sulle vie dirette costose, e il costo sale. Il flusso frazionario, libero di dividersi, distribuisce ogni domanda su entrambi i percorsi e rientra in tutte le capacità contemporaneamente. È così che ottieni un costo frazionario inferiore al costo minimo legale non frazionabile. Le cifre di Rybin per la sua istanza sono 58 e 60.

Sarò onesto su un limite. 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 io abbia verificato arco per arco. Quindi non metterò in scena una derivazione pulita del 58 fingendo che sia la sua. Quello che posso fare è consegnarti un’istanza autosufficiente che mostra lo stesso meccanismo, abbastanza piccola da essere controllata per forza bruta, così puoi vedere con i tuoi occhi cosa significa "il frazionario batte ogni non frazionabile legale". 

Quattro prompt, diverse ore

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

Il log della chat condiviso da Rybin mostra che il modello ha fallito all’inizio, e ha fallito onestamente. 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 controesempio valido sarebbe stato falso.

Invitato a proseguire, ha riprovato e di nuovo non ha trovato nulla, descrivendo come ogni costruzione promettente continuasse a far spuntare un’opzione di instradamento nascosta in più che distruggeva la separazione costo-congestione una volta elencati tutti i percorsi. Un terzo prompt, che chiedeva una strategia più pulita, ha portato a un quadro più ristretto e ancora nessun risultato finito.

Non è "quattro prompt, fatto". Sono ore di un modello che sbatte contro muri e dice la verità in proposito. Il muro specifico contro cui ha continuato a sbattere, appare un percorso extra che rovina la separazione, è esattamente ciò che la costruzione finale è stata progettata per prevenire, vincolando ciascun terminal a esattamente due percorsi in modo che l’intero spazio di instradamento sia di otto opzioni che puoi elencare a mano. Tieni a mente questa modalità di fallimento. Stai per imbatterti in essa tu stesso.

Il quarto prompt, a quanto pare qualcosa di simile a "ne ho abbastanza dei tuoi fallimenti, per favore chiudi 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. Anche i rifiuti precedenti lo sono stati; erano autovalutazioni oneste.

Verificalo tu

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

Un rapido caveat prima del codice. Quanto segue non è il grafo di Rybin. È un’istanza schematica che ho costruito per essere rigorosa, in cui ogni terminal ha davvero esattamente due percorsi, l’aritmetica torna e il gap è reale. Ti mostra la forma di un controesempio del genere e la tecnica per verificarlo. Da sola, non confuta nulla, e subito dopo che l’avrai eseguita ti spiegherò perché.

Il setup: 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 organizzati 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 propria domanda sulla via economica e 3/5 su quella costosa, per un costo pari a 30 x 3/5 x 3 = 54. Ogni strada porta così 4 + 4 = 8 unità in frazione, e il budget di congestione è quel carico più D, quindi 18.

Ora guarda cosa fa l’instradamento non frazionabile. Due terminal che vanno entrambi al risparmio scaricano 10 + 10 = 20 unità sulla loro strada condivisa, sopra il budget di 18. Quindi al massimo un terminal può instradare in modo economico; gli altri due pagano 30 ciascuno. Costo minimo legale non frazionabile: 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 otterrai un costo frazionario di 54, un costo minimo legale non frazionabile di 60 e un gap di 6. Le tre righe in sovraccarico sono i tre conflitti a coppie; gli unici instradamenti che sopravvivono tengono 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 ciascun terminal ha davvero due percorsi e non di più. Se costruisci questo grafo con strade e nodi reali, tende ad apparire un quarto percorso economico, per pura combinatoria. Un terminal trova una terza strada di casa economica che resta sotto budget, e il gap si chiude. Quel percorso extra è l’esatto fallimento che il modello ha riportato nei primi tre tentativi. Un gadget pulito e simmetrico che abbatte 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à bersaglio è reale. Stabilire se un dato grafo abbia effettivamente quella proprietà, senza perdite, è la parte difficile, ed è il motivo per cui la vera istanza di Rybin è un punto tarato in una famiglia di parametri e non un triangolo ordinato.

Cosa resta irrisolto

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

Il grafo esatto pubblicato non è stato ricostruito in modo indipendente da una fonte primaria che io abbia trovato. I numeri circolanti 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 la sua istanza si inserisce in un’infinita famiglia a tre parametri sugli stessi nodi, il che renderebbe il risultato più ricco di una singola fortunata coincidenza. Incoraggiante, ma è un controllo informale della comunità, non un rapporto di referaggio. Considera il 58 vs 60 come un’affermazione ben supportata, non un fatto assodato.

Il teorema sulla congestione del 1999 resta intatto.

Parte di un modello ricorrente

Questa storia non è un caso isolato. È la terza congettura che si dice sia caduta grazie all’assistenza dell’IA in circa tre mesi, e vale la pena soffermarsi sul modello che si sta delineando.

Il 20 luglio, Claude Fable 5 avrebbe aiutato il matematico Levent Alpöge a trovare un controesempio alla congettura di Jacobiano, un problema vecchio di 87 anni. Prima ancora, a maggio, si è detto che un modello di OpenAI avesse confutato la congettura della distanza unitaria 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 strutturato in stile Codex 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 confutare 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’IA risolve la matematica". Quello che stiamo vedendo è l’IA che lavora come partner di ricerca paziente e combinatoriamente esaustivo: capace di enumerare famiglie di parametri, mantenere in memoria le modalità di fallimento tra i tentativi e dire la verità quando una costruzione non si chiude. È una capacità specifica e utile. E se vuoi capire dove è probabile che colpisca la prossima volta, la domanda da farti non è quali congetture sono più vecchie, ma quali possono essere spezzate da un singolo testimone verificabile.