OpenAI afferma che un suo modello interno ha confutato l’Exponential Time Hypothesis (ETH), una congettura dell’informatica teorica vecchia di 27 anni. Poche ore dopo l’annuncio, Anthropic ha pubblicato una propria confutazione, attribuita a Claude. Due laboratori, lo stesso risultato, la stessa data di scoperta.
L’ETH sostiene che alcuni problemi logici, come il 3-SAT, non possano essere risolti in tempo inferiore all’esponenziale. È stata usata in centinaia di articoli per dimostrare che molti altri problemi, dai grafi ai database fino alla biologia computazionale, sono difficili da risolvere in fretta. Se cade, alcuni di quei problemi potrebbero avere soluzioni più rapide del previsto.
I dettagli tecnici coincidono. Il paper di OpenAI, intitolato “The Exponential Time Hypothesis is false”, descrive un algoritmo deterministico che conta le soluzioni di formule CNF a larghezza fissa in tempo subesponenziale e spazio polinomiale. Con n variabili servono circa 2^(n/√log n) passi. Secondo OpenAI il modello ha trovato la prova il 16 ottobre e il giorno dopo Lean, un linguaggio che verifica le dimostrazioni a macchina, l’ha controllata. Anthropic indica la stessa data del 16 ottobre, dice che il suo modello ha trovato l’algoritmo senza intervento umano e allega anche una formalizzazione in Lean.
La verifica spetta agli autori stessi dell’ipotesi. Russell Impagliazzo e Ramamohan Paturi guideranno un esame indipendente insieme a Ryan Williams del MIT. OpenAI ha pubblicato la prova scritta dal modello e la formalizzazione, e ha promesso di rendere pubblici tutti i dati grezzi. Non tutti reagiscono con entusiasmo. Il matematico di Anthropic Levent Alpöge ha avanzato dubbi sul fatto che OpenAI sia partita da soluzioni già esistenti, come riporta TechCrunch.
Il risultato non cambia nulla per la sicurezza informatica. Non dimostra che P sia uguale a NP, quindi non minaccia la crittografia che protegge Bitcoin ed Ethereum. Anthropic avverte che il risultato teorico non garantisce un’accelerazione pratica sui problemi reali. L’algoritmo batte il limite esponenziale previsto dall’ETH, ma resta troppo lento per l’uso concreto.
L’annuncio fa parte di una serie. OpenAI ha dichiarato il 26 ottobre altri due risultati su questioni scientifiche aperte, dopo una soluzione proposta per Navier-Stokes e centinaia di manoscritti matematici. Se la revisione di Impagliazzo, Paturi e Williams confermerà la prova, i due laboratori si contenderanno la paternità di una scoperta arrivata in parallelo. Se emergeranno falle, la corsa alla scienza fatta dalle macchine dovrà fare i conti con la verifica umana.
