OpenAI ha annunciato il 26 ottobre 2026 che un suo sistema avrebbe prodotto un risultato che, secondo l’azienda, confuterebbe l’Exponential Time Hypothesis (ETH), una congettura sulla complessità nel caso peggiore della soddisfacibilità booleana. OpenAI data al 16 ottobre il risultato formulato in linguaggio naturale e al 17 ottobre la sua formalizzazione in Lean. La portata del teorema formalizzato riguarda il conteggio esatto delle soluzioni di formule k-CNF; limiti temporali più stretti sono attribuiti separatamente al manoscritto.
Che cosa sostiene OpenAI su ETH
Secondo l’annuncio di OpenAI, il sistema interno ha prodotto un risultato che confuterebbe ETH. Il 26 ottobre l’azienda ha anche annunciato un gruppo esterno guidato da Russell Impagliazzo e Ramamohan Paturi, di UC San Diego, e Ryan Williams, del MIT, con il compito di esaminare e spiegare il risultato. Il 28 ottobre 2026 ExplainX riferiva che non era stata riportata una conferma indipendente.
ETH riguarda i limiti di tempo per risolvere problemi di soddisfacibilità booleana. La formalizzazione descritta da OpenAI si concentra invece sul conteggio: quante assegnazioni di valori rendono vera una formula. È una domanda più precisa del semplice stabilire se esista almeno una soluzione.
Che cosa formalizza Lean
La documentazione ufficiale sull’ambito Lean descrive un algoritmo deterministico che conta esattamente le assegnazioni soddisfacenti di formule k-CNF codificate in forma canonica, per ogni k ≥ 2 fissato. In una formula k-CNF, le clausole contengono al massimo k letterali.
Per questo teorema, il limite di tempo riportato è (L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√log n)}. Qui L è la lunghezza in bit della codifica e n il numero di variabili. La documentazione indica inoltre che, a ogni passo, la macchina ha visitato al massimo (L+1)^{O_k(1)} celle di nastro in totale.
Il limite del manoscritto è distinto
La stessa pagina attribuisce al manoscritto un limite temporale più stretto: (n+m)^{O_k(1)} 2^{O_k(n log log n/√log n)}, dove m è il numero di clausole. Per il caso in cui m ≤ Dn, con D > 0 fissato, riporta anche (n+m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)}.
Queste espressioni non sono il limite temporale indicato per il teorema formalizzato in Lean: la pagina separa la propria formulazione dai limiti che attribuisce al manoscritto. La distinzione aiuta a capire quale enunciato è codificato nel sistema di dimostrazione e quali prestazioni vengono invece dichiarate nel testo del manoscritto.
Che cosa cambia per la teoria e per il software
L’annuncio di OpenAI non sostiene di aver dimostrato P = NP. L’azienda osserva che ETH è stata usata in centinaia di articoli per ricavare risultati condizionali sulla difficoltà di problemi in campi come teoria dei grafi, biologia computazionale, basi di dati e geometria computazionale.
Un limite asintotico descrive come cresce il tempo teorico al crescere della dimensione dell’input; da solo non indica quanto impieghi un programma su un computer reale. OpenAI afferma che trasformare i progressi teorici in miglioramenti pratici richiederà ulteriore ricerca significativa.
Per un’introduzione visiva a ETH e alla differenza tra limiti asintotici e prestazioni pratiche, Adem B10 usa un rompicapo con interruttori come esempio semplificato. Non è l’algoritmo di OpenAI; il video è in inglese.
