Un modello di OpenAI ha confutato l’Exponential Time Hypothesis (ETH) trovando un metodo più veloce per un classico rompicapo logico. A supporto della scoperta c’è anche una prova verificata da una macchina, che ribalta un’ipotesi su cui i ricercatori facevano affidamento da 27 anni.
Questo risultato non dimostra che P sia uguale a NP, ossia il più ampio quesito che sta dietro la crittografia moderna. Di conseguenza, l’algoritmo non rappresenta una minaccia diretta per la crittografia che protegge Bitcoin (BTC) ed Ethereum.
Perché era importante l’Exponential Time Hypothesis?
L’ipotesi riguarda il problema 3-SAT, un rompicapo composto da interruttori vero/falso e regole che li collegano. L’obiettivo è trovare una configurazione degli interruttori che soddisfi contemporaneamente tutte le regole.
Verificare una soluzione proposta è facile. Trovarla è difficile, perché ogni interruttore aggiunto raddoppia le combinazioni possibili.
Russell Impagliazzo e Ramamohan Paturi hanno proposto l’ETH nel 1999. Nonostante la sigla sia la stessa, non ha nulla a che vedere con il ticker di Ethereum.
L’ipotesi sostiene che nessun algoritmo possa evitare questa crescita esponenziale nei casi peggiori.
I ricercatori l’hanno considerata come un pilastro fondamentale. Secondo OpenAI, centinaia di studi su teoria dei grafi, biologia computazionale e database hanno costruito risultati di complessità basandosi su di essa.
Come ha fatto un’AI a trovare un percorso più breve che gli esperti non avevano visto?
Il sistema di OpenAI ha prodotto una dimostrazione in linguaggio naturale il 16 ottobre. Il giorno successivo, il team l’ha formalizzata con Lean, un software che verifica passo per passo ogni ragionamento logico.
L’algoritmo pubblicato gestisce input con n variabili in circa 2^(n/√log n) passaggi. Questo risultato supera la soglia esponenziale che l’ETH aveva previsto, ma resta comunque troppo lento per un’applicazione pratica.
OpenAI avverte che per rendere realmente più veloci questi algoritmi, occorrono molte altre ricerche.
Impagliazzo e Paturi, entrambi alla UC San Diego, ora guideranno la revisione insieme a Ryan Williams del MIT. In altre parole, gli stessi autori dell’ipotesi stanno verificando la sua confutazione.
Nel frattempo, OpenAI non rivendica alcun merito scientifico per la scoperta, mantenendo la stessa posizione assunta nella precedente disputa Navier-Stokes.
Scott Aaronson, professore di informatica all’Università del Texas di Austin, ha raccontato come ha appreso la notizia.
“I miei studenti sono appena venuti nel mio ufficio per dirmi che un modello di OpenAI ha ora confutato la Exponential Time Hypothesis”
Scott Aaronson tramite Shtetl-Optimized
Confutare l’ETH significa che P uguale NP?
No. P contro NP si chiede se ogni problema con soluzioni verificabili rapidamente possa anche essere risolto rapidamente.
L’ETH era un’affermazione più restrittiva rispetto a P ≠ NP. Quindi, la sua confutazione lascia ancora aperta la questione più ampia.
Immagina una montagna tra due valli. L’AI ha trovato un sentiero più corto sopra la cresta, non un tunnel che la attraversa.
Greg Brockman, presidente e co-fondatore di OpenAI, ha sottolineato lo stesso aspetto poche ore dopo l’annuncio.
La distinzione è importante per chi possiede crypto. Le firme di Bitcoin si basano sulla crittografia a curve ellittiche, un problema matematico difficile che questo algoritmo non affronta.
Benjamin Cowen, membro del Market Intelligence Expert Council di BeInCrypto, ha affrontato la questione.
Ma per essere chiari, confutare l’Exponential Time Hypothesis non dimostrerebbe che P = NP, né significherebbe che Bitcoin o Ethereum siano compromessi.
Exponential Time Hypothesis: cosa succede quando le macchine superano i loro creatori?
In passato alcune convinzioni sull’impossibilità sono già crollate. Nel 1960 Anatoly Karatsuba ha confutato la congettura sulla moltiplicazione di Andrey Kolmogorov in circa una settimana.
Allo stesso modo, nel 1969 Volker Strassen voleva dimostrare che la moltiplicazione standard delle matrici fosse ottimale, ma ha trovato invece un metodo più veloce.
Ciò che cambia oggi è chi trova la scorciatoia. Le macchine producono le dimostrazioni, mentre gli umani si sforzano di comprenderle.
Nello stesso annuncio OpenAI ha riferito di ulteriori prove in analisi armonica e fisica delle particelle.
Questa rapidità incide sulle risorse digitali. Il crittografo Matthew Green ha già avvertito che le AI potrebbero indebolire la matematica alla base dei wallet.
Cowen ha interpretato l’insegnamento su più ampia scala in chiave di mercato. Secondo lui, settori apparentemente lontani dalla finanza possono potenzialmente cambiare i mercati.
Per un settore basato su ipotesi di complessità, ogni nuovo risultato dell’AI oggi diventa anche uno stress test.
