Analisi
OpenAI e Anthropic affermano che l'IA ha confutato l'ipotesi del tempo esponenziale, ma la dimostrazione non è certificata e il guadagno inizia solo con input astronomici
OpenAI e Anthropic dicono che l'IA ha confutato l'ipotesi del tempo esponenziale. Impagliazzo parla di notizia scioccante, ma la revisione è in corso.
Russell Impagliazzo, che negli anni Novanta ha co-proposto l'ipotesi del tempo esponenziale (ETH), ha definito una notizia molto scioccante la sua confutazione prodotta da IA, secondo la stampa ripresa da AI Weekly il 7 novembre. L'inquadramento richiede cautela: due articoli, uno di OpenAI e uno di Anthropic, annunciati il 26 ottobre, rivendicano un algoritmo più veloce per 3-SAT; i revisori dicono che la loro partecipazione non è una certificazione, il risultato non risolve P contro NP e il guadagno supera la forza bruta solo con dimensioni di input ben oltre ciò che si può memorizzare. Trasparenza: Anthropic sviluppa Claude, che aiuta a scrivere gli articoli di questo sito, e ha pubblicato uno dei due articoli.
L'essenziale
- L'annuncio: l'articolo di OpenAI (67 pagine) e quello di Anthropic (49) presentano algoritmi per 3-SAT in tempo 2^o(n), il che contraddirebbe l'ETH. Entrambi dicono che l'IA ha contribuito molto e che le dimostrazioni sono state controllate in Lean, secondo AI Weekly.
- Cosa diceva l'ETH: 3-SAT non si risolve in tempo sub-esponenziale. È più forte di P diverso da NP e serve a mostrare che molti algoritmi sono quasi ottimali, secondo Wikipedia.
- Verifica finora: un gruppo composto da Impagliazzo, Ryan Williams e Ramamohan Paturi ha esaminato il lavoro. La loro dichiarazione congiunta dice che la partecipazione non va presa come certificazione, e Williams ha parlato di parti dall'aspetto alieno che la comunità deve studiare.
- Portata pratica: stime esterne collocano il punto di pareggio con la forza bruta intorno a 10^2.389 variabili per il limite di OpenAI e 10^10.000 per il caso a cinque clausole di Anthropic. I solver SAT attuali e la crittografia non sono toccati.
Cosa è dimostrato e cosa no
Un algoritmo sub-esponenziale non è polinomiale, quindi entrambi i laboratori dicono che il risultato non risolve P contro NP, e OpenAI precisa che l'accelerazione non si estende ai problemi NP in generale. Il controllo in Lean conferma la logica di un enunciato formale, ma i revisori hanno chiesto i dati grezzi e una conferenza, che OpenAI ha accettato di finanziare, secondo AI Weekly. Date riportate: l'IA ha trovato l'argomento in linguaggio naturale il 16 ottobre, è stato formalizzato il giorno dopo e gli articoli sono usciti il 26 ottobre.
Chip e crittografia: cosa è stabilito
L'ETH riguarda il caso peggiore, quindi l'effetto immediato è teorico e tocca i limiti inferiori che ne dipendono. Parlare di verifica dei chip più rapida o di crittografia indebolita è speculazione di lungo periodo. BeInCrypto e Let's Data Science dicono che la crittografia attuale e i solver industriali non sono toccati, e AI Weekly riprende un informatico che giudica fuorviante un articolo di stampa. HackerNoon dice che gli autori applicano il metodo anche alle curve ellittiche sulla carta; non abbiamo visto che sia verificato.
Che cosa non è accertato
- Certificazione delle dimostrazioni da parte del gruppo di revisione: in attesa, secondo AI Weekly.
- Qualsiasi accelerazione utilizzabile su istanze SAT reali: non dimostrata; le soglie sono astronomiche.
- Qualsiasi attacco pratico alla crittografia o agli strumenti di progettazione dei chip: non stabilito.
- Se le affermazioni del Wall Street Journal e del New York Times su chip e crittografia vanno oltre la speculazione: non le abbiamo lette direttamente.
Tabella riassuntiva
| Punto | Che cosa risulta al 7 novembre 2026 | Fonte |
|---|---|---|
| Annuncio | Due articoli annunciati il 26 ottobre 2026 (OpenAI 67 pagine, Anthropic 49) | AI Weekly |
| Risultato rivendicato | 3-SAT in tempo 2^o(n), controllato in Lean | AI Weekly |
| Dimensione di pareggio | Circa 10^2.389 variabili (OpenAI), 10^10.000 (caso a cinque clausole di Anthropic) | AI Weekly |
| Revisori | Impagliazzo, Williams, Paturi; dichiarazione congiunta: non una certificazione | AI Weekly |
| P contro NP | Non risolto, secondo entrambi i laboratori | Let's Data Science |
FAQ
L'IA ha dimostrato che P è uguale a NP?
No. L'algoritmo rivendicato è sub-esponenziale, non polinomiale, ed entrambi i laboratori dicono che P contro NP non è risolto.
La crittografia è più debole?
Non in pratica. I media consultati dicono che la crittografia in uso non è toccata e il guadagno compare solo con input assurdamente grandi.
La dimostrazione è confermata?
Non ancora certificata. Le dimostrazioni sono state controllate in Lean, ma i revisori dicono che la loro partecipazione non è una certificazione e lo studio continua.
Metodo e limiti
Fonti verificate l'8 novembre 2026. Non abbiamo letto i due articoli, i file Lean né gli articoli di stampa originali; ci siamo basati su AI Weekly, Let's Data Science, HackerNoon, BeInCrypto e Wikipedia. Trasparenza: Anthropic sviluppa Claude, che aiuta a scrivere gli articoli di questo sito. Non è un consiglio di investimento né di sicurezza.
Fonti
- AI Weekly: OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo (verificato il 2026-11-08)
- Let's Data Science: OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16. (verificato il 2026-11-08)
- HackerNoon: OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis (verificato il 2026-11-08)
- BeInCrypto: OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe? (verificato il 2026-11-08)
- Wikipedia: Exponential time hypothesis (verificato il 2026-11-08)
Avete notato un errore in questo articolo? Segnalatelo · La nostra politica sulle correzioni