OpenAI e Anthropic hanno entrambe pubblicato una dimostrazione secondo cui l’ipotesi del tempo esponenziale è falsa.
ETH è un’ipotesi della teoria dell’informatica, vecchia di 27 anni, secondo cui alcuni problemi non possono mai essere risolti molto più velocemente del brute force. Ora, i principali laboratori di AI dicono che semplicemente non è vero.
Se le dimostrazioni reggono, si tratta del risultato generato da AI più significativo nella storia dell’informatica. Inoltre, costringono a ripensare letteralmente centinaia di articoli di ricerca che assumevano vera l’ETH.
In questo articolo spieghiamo cosa significa davvero l’ipotesi del tempo esponenziale, insieme a P vs NP, che è correlato. Vedremo anche cosa affermano esattamente i due laboratori, come sono state verificate le dimostrazioni e cosa cambia (e cosa no) per la crittografia.
P vs NP in parole semplici
P contro NP chiede se ogni problema la cui risposta è facile da verificare sia anche facile da risolvere. È uno dei sette Millennium Prize Problems, ed è ancora aperto dopo questa notizia.
Un Sudoku è l’esempio classico. Verificare una griglia compilata richiede pochi secondi: controlli ogni riga, colonna e riquadro per vedere se ci sono ripetizioni. Trovare la soluzione a partire da una griglia quasi vuota può richiedere molto più tempo, e il divario esplode man mano che la griglia cresce.
- P è la classe di problemi che un computer può risolvere in tempo polinomiale, cioè il lavoro cresce come n², n³ e così via al crescere della dimensione dell’input n.
- NP è la classe di problemi le cui soluzioni proposte un computer può verificare in tempo polinomiale.
Ogni problema in P è anche in NP. La domanda aperta è se valga il contrario. La maggior parte degli informatici ritiene che P ≠ NP, quindi che alcuni problemi siano fondamentalmente più difficili da risolvere che da verificare. La crittografia moderna si basa su questa convinzione: cifrare è facile, ma decifrare senza la chiave dovrebbe essere difficile.
Che cos’è l’ipotesi del tempo esponenziale?
L’ETH è più incisiva: afferma che uno specifico problema in NP, 3-SAT, richiede tempo esponenziale indipendentemente da quanto sia astuto l’algoritmo. Russell Impagliazzo e Ramamohan Paturi della UC San Diego l’hanno proposta alla fine degli anni ’90, con Francis Zane che ha contribuito al lavoro fondativo.
Il problema 3-SAT
In 3-SAT, hai una formula composta da n variabili vero/falso e un elenco di clausole. Ogni clausola unisce tre condizioni con OR, ad esempio "x₁ è vera OR x₄ è falsa OR x₇ è vera". Il compito è trovare un’assegnazione delle variabili che soddisfi tutte le clausole contemporaneamente.
Il brute force prova tutte le 2ⁿ assegnazioni, quindi ogni variabile in più raddoppia il lavoro. È facile vedere come intorno alle 100 variabili diventi senza speranza.
Cosa afferma l’ETH
L’ETH afferma che esiste una costante c > 1 tale che nessun algoritmo risolve 3-SAT più velocemente di cⁿ. Algoritmi ingegnosi possono ridurre la base al di sotto di 2, ma mai fino a qualcosa di subesponenziale. Formalmente: esiste δ > 0 tale che 3-SAT non può essere risolto in tempo O(2δn).
Per decenni, i progressi hanno seguito questo quadro. I ricercatori continuavano ad abbassare la base, ma rimaneva ben al di sopra di 1. Poiché 3-SAT può essere convertito in molti altri problemi, l’ETH è diventata un’ipotesi di lavoro. È stata usata per argomentare che problemi come Clique, Vertex Cover, Independent Set e altri non possono essere risolti molto più velocemente neanche loro.
Come si confronta il nuovo risultato
| Approccio | Tempo di esecuzione per 3-SAT | Cresce esponenzialmente? |
|---|
| Brute force | 2ⁿ | Sì |
| Migliore noto prima di ott 2026 (deterministico) | circa 1,328ⁿ | Sì |
| Migliore noto prima di ott 2026 (randomizzato) | circa 1,308ⁿ | Sì |
| OpenAI e Anthropic (ott 2026) | 2^O(n log log n / √log n) | No: subesponenziale |
Il nuovo limite si scrive in breve 2o(n). Il costo per variabile aggiunta si avvicina a 1 al crescere di n, che è esattamente ciò che l’ETH diceva fosse impossibile.
Cosa hanno annunciato OpenAI e Anthropic
Entrambi i laboratori hanno raggiunto in modo indipendente sostanzialmente lo stesso limite subesponenziale, e hanno supportato i loro articoli con dimostrazioni verificate automaticamente con l’assistente alle dimostrazioni Lean.
| | OpenAI | Anthropic |
|---|
| Articolo | "The Exponential Time Hypothesis Is False" (67 pagine) | "A 2o(n) Time Algorithm for 3-SAT" (49 pagine) |
| Modello | Modello interno senza nome | Modello di ricerca Claude interno, accreditato come autore |
| Idea centrale trovata | 16 ottobre 2026 | 16 ottobre 2026 |
| Reso pubblico | 26 ottobre 2026 | 26–27 ottobre 2026 |
| Verifica | Dimostrazione in Lean di un limite leggermente più debole che comunque confuta l’ETH | Dimostrazione in Lean 4 contro Mathlib, ricontrollata da un secondo kernel |
| Ulteriori affermazioni | Il miglioramento non si estende a tutto NP | Confuta anche la strong ETH (SETH); nuovo limite inferiore per circuiti |
Anthropic afferma che Claude ha trovato l’algoritmo centrale senza input umano dopo aver prodotto circa 14 milioni di token di output. Il suo metodo usa reti tensoriali e argomenti di rango. I ricercatori hanno poi aiutato con la stesura finale dell’articolo.
Perché entrambi i laboratori l’hanno trovata lo stesso giorno?
Nessuno dei due laboratori ha spiegato le tempistiche. L’articolo di Anthropic definisce i due risultati indipendenti e concomitanti, e i due testi percorrono strade matematiche diverse per arrivare in sostanza allo stesso limite.
Alcuni elementi di contesto rendono la sovrapposizione meno sorprendente di quanto sembri inizialmente. Entrambi i laboratori hanno indirizzato i loro modelli verso lunghe liste di problemi aperti, e OpenAI da sola ha rilasciato centinaia di manoscritti matematici generati da AI a inizio ottobre. L’ETH è uno dei bersagli più noti nel campo, e entrambi i modelli hanno imparato dalla stessa ricerca pubblicata. La scoperta indipendente e simultanea è anche un vecchio schema nella scienza, come con Newton e Leibniz per il calcolo infinitesimale o Darwin e Wallace per la selezione naturale.
Quanto sono solide le dimostrazioni?
Lean conferma che un enunciato formale segue logicamente dai suoi assiomi. Non può confermare che l’enunciato formale dica la stessa cosa dell’articolo. Anthropic nota che nessuna macchina verifica questa corrispondenza, e OpenAI afferma che il suo file Lean dimostra un limite leggermente più debole rispetto al titolo.
Ora, gli stessi ricercatori che hanno proposto il problema, Impagliazzo e Paturi, insieme a Ryan Williams del MIT, stanno organizzando workshop per valutare se gli enunciati formali catturino davvero l’ETH. La loro lettera sottolinea che partecipare alla revisione non equivale a un avallo. Al momento della stesura dell’articolo, nessuno aveva pubblicamente trovato un errore.
Williams ha detto che parti della dimostrazione di OpenAI sembrano di routine, mentre "due o tre parti dall’aspetto alieno" necessitano ancora di scrutinio. Impagliazzo, uno degli autori dell’ETH, ha descritto il risultato come profondamente sorprendente.
Cosa cambia e cosa no
In pratica, oggi non cambia quasi nulla (fiù): i nuovi algoritmi battono il brute force solo su input molto più grandi di quanto un computer potrà mai contenere.
Niente solver SAT più veloci
L’articolo di Anthropic afferma che il suo metodo supera il brute force solo su input astronomicamente grandi. Per formule tipiche con cinque clausole per variabile, il punto di incrocio è un numero con circa 10.000 cifre. Nel caso più generale, è un numero con all’incirca 100 milioni di cifre.
Gli autori affermano anche che il loro approccio è improbabile che aiuti su qualsiasi cosa al di sotto di circa 10 milioni di variabili. I solver SAT usati nella verifica dei chip, nella schedulazione e nella pianificazione non diventeranno più veloci grazie a questo risultato.
La crittografia non è compromessa
Il risultato non tocca P vs NP. Nessuno lo sostiene. OpenAI dice di aver verificato se l’algoritmo rompe sistemi crittografici reali ed è abbastanza fiduciosa che non lo faccia.
La teoria si riscrive
L’impatto maggiore è sulla ricerca. I risultati di durezza basati su ETH o SETH ora necessitano di nuovi fondamenti, e alcuni ricercatori hanno detto che anni del proprio lavoro potrebbero dover essere rivisti. Non cade tutto, però. Anthropic nota che il risultato non confuta il problema dei vettori ortogonali, che supporta molti risultati di complessità fine-grained.
Perché è importante per l’AI
Il punto non è tanto 3-SAT quanto chi ha trovato la risposta: due sistemi di AI hanno indipendentemente ribaltato una congettura a cui gli esperti umani si affidavano da una generazione.
L’AI come collaboratore di ricerca
I ricercatori descrivono ormai nuovi risultati di AI che arrivano ogni una o due settimane, sconvolgendo progetti già in corso. Strumenti formali come Lean stanno diventando centrali perché permettono agli umani di fidarsi di una lunga dimostrazione scritta da una macchina senza doverla ri-derivare riga per riga.
Scorciatoie nascoste e auto-miglioramento
L’ETH sintetizzava la convinzione che alcuni problemi di ricerca non avessero scorciatoie intelligenti. Se questa convinzione è sbagliata, anche altri problemi apparentemente duri potrebbero nascondere scorciatoie.
Penso alla scoperta di algoritmi come un’area in cui tali scorciatoie potrebbero contare molto per il miglioramento ricorsivo, l’idea di sistemi di AI che aiutano a progettare AI migliori. Usare l’AI per trovare algoritmi più veloci è un percorso concreto in quella direzione, anche se nulla in questo risultato lo realizza direttamente oggi.
Cosa significa per chi lavora con i dati
Per chi costruisce con i dati, emergono tre lezioni:
- La teoria della complessità non è solo accademia: Sapere perché un problema è NP-hard ti dice quando pensare a euristiche, approssimazioni o solver invece che a una ricerca esatta.
- La verifica è una competenza: Man mano che l’AI genera più codice e analisi, controllarne l’output (con test, dimostrazioni o pipeline riproducibili) conta tanto quanto produrlo.
- Le asintotiche possono ingannare: Un algoritmo "più veloce" in teoria può essere inutile alle dimensioni del mondo reale.
Conclusione
Se le dimostrazioni supereranno la revisione degli esperti, l’ipotesi del tempo esponenziale entrerà nel breve elenco di congetture ampiamente credute che si sono rivelate false (come la congettura sulla somma di potenze di Eulero). Ma P vs NP resta aperto e la crittografia è al sicuro per ora.
I prossimi traguardi da seguire sono i workshop di revisione guidati dagli autori originali dell’ETH, reimplementazioni indipendenti degli algoritmi e l’eventuale ulteriore affinamento del limite.
Per costruire le basi dietro storie come questa, esplora i nostri corsi su strutture dati e algoritmi, programmazione in Python e machine learning. Coprono il pensiero Big-O che rende leggibili risultati come questo.
OpenAI e Anthropic hanno entrambe pubblicato una dimostrazione secondo cui l’ipotesi del tempo esponenziale è falsa.
ETH è un’ipotesi della teoria dell’informatica, vecchia di 27 anni, secondo cui alcuni problemi non possono mai essere risolti molto più velocemente del brute force. Ora, i principali laboratori di AI dicono che semplicemente non è vero.
Se le dimostrazioni reggono, si tratta del risultato generato da AI più significativo nella storia dell’informatica. Inoltre, costringono a ripensare letteralmente centinaia di articoli di ricerca che assumevano vera l’ETH.
In questo articolo spieghiamo cosa significa davvero l’ipotesi del tempo esponenziale, insieme a P vs NP, che è correlato. Vedremo anche cosa affermano esattamente i due laboratori, come sono state verificate le dimostrazioni e cosa cambia (e cosa no) per la crittografia.
P vs NP in parole semplici
P contro NP chiede se ogni problema la cui risposta è facile da verificare sia anche facile da risolvere. È uno dei sette Millennium Prize Problems, ed è ancora aperto dopo questa notizia.
Un Sudoku è l’esempio classico. Verificare una griglia compilata richiede pochi secondi: controlli ogni riga, colonna e riquadro per vedere se ci sono ripetizioni. Trovare la soluzione a partire da una griglia quasi vuota può richiedere molto più tempo, e il divario esplode man mano che la griglia cresce.
Ogni problema in P è anche in NP. La domanda aperta è se valga il contrario. La maggior parte degli informatici ritiene che P ≠ NP, quindi che alcuni problemi siano fondamentalmente più difficili da risolvere che da verificare. La crittografia moderna si basa su questa convinzione: cifrare è facile, ma decifrare senza la chiave dovrebbe essere difficile.
Che cos’è l’ipotesi del tempo esponenziale?
L’ETH è più incisiva: afferma che uno specifico problema in NP, 3-SAT, richiede tempo esponenziale indipendentemente da quanto sia astuto l’algoritmo. Russell Impagliazzo e Ramamohan Paturi della UC San Diego l’hanno proposta alla fine degli anni ’90, con Francis Zane che ha contribuito al lavoro fondativo.
Il problema 3-SAT
In 3-SAT, hai una formula composta da n variabili vero/falso e un elenco di clausole. Ogni clausola unisce tre condizioni con OR, ad esempio "x₁ è vera OR x₄ è falsa OR x₇ è vera". Il compito è trovare un’assegnazione delle variabili che soddisfi tutte le clausole contemporaneamente.
Il brute force prova tutte le 2ⁿ assegnazioni, quindi ogni variabile in più raddoppia il lavoro. È facile vedere come intorno alle 100 variabili diventi senza speranza.
Cosa afferma l’ETH
L’ETH afferma che esiste una costante c > 1 tale che nessun algoritmo risolve 3-SAT più velocemente di cⁿ. Algoritmi ingegnosi possono ridurre la base al di sotto di 2, ma mai fino a qualcosa di subesponenziale. Formalmente: esiste δ > 0 tale che 3-SAT non può essere risolto in tempo O(2δn).
Per decenni, i progressi hanno seguito questo quadro. I ricercatori continuavano ad abbassare la base, ma rimaneva ben al di sopra di 1. Poiché 3-SAT può essere convertito in molti altri problemi, l’ETH è diventata un’ipotesi di lavoro. È stata usata per argomentare che problemi come Clique, Vertex Cover, Independent Set e altri non possono essere risolti molto più velocemente neanche loro.
Come si confronta il nuovo risultato
Il nuovo limite si scrive in breve 2o(n). Il costo per variabile aggiunta si avvicina a 1 al crescere di n, che è esattamente ciò che l’ETH diceva fosse impossibile.
Cosa hanno annunciato OpenAI e Anthropic
Entrambi i laboratori hanno raggiunto in modo indipendente sostanzialmente lo stesso limite subesponenziale, e hanno supportato i loro articoli con dimostrazioni verificate automaticamente con l’assistente alle dimostrazioni Lean.
Anthropic afferma che Claude ha trovato l’algoritmo centrale senza input umano dopo aver prodotto circa 14 milioni di token di output. Il suo metodo usa reti tensoriali e argomenti di rango. I ricercatori hanno poi aiutato con la stesura finale dell’articolo.
Perché entrambi i laboratori l’hanno trovata lo stesso giorno?
Nessuno dei due laboratori ha spiegato le tempistiche. L’articolo di Anthropic definisce i due risultati indipendenti e concomitanti, e i due testi percorrono strade matematiche diverse per arrivare in sostanza allo stesso limite.
Alcuni elementi di contesto rendono la sovrapposizione meno sorprendente di quanto sembri inizialmente. Entrambi i laboratori hanno indirizzato i loro modelli verso lunghe liste di problemi aperti, e OpenAI da sola ha rilasciato centinaia di manoscritti matematici generati da AI a inizio ottobre. L’ETH è uno dei bersagli più noti nel campo, e entrambi i modelli hanno imparato dalla stessa ricerca pubblicata. La scoperta indipendente e simultanea è anche un vecchio schema nella scienza, come con Newton e Leibniz per il calcolo infinitesimale o Darwin e Wallace per la selezione naturale.
Quanto sono solide le dimostrazioni?
Lean conferma che un enunciato formale segue logicamente dai suoi assiomi. Non può confermare che l’enunciato formale dica la stessa cosa dell’articolo. Anthropic nota che nessuna macchina verifica questa corrispondenza, e OpenAI afferma che il suo file Lean dimostra un limite leggermente più debole rispetto al titolo.
Ora, gli stessi ricercatori che hanno proposto il problema, Impagliazzo e Paturi, insieme a Ryan Williams del MIT, stanno organizzando workshop per valutare se gli enunciati formali catturino davvero l’ETH. La loro lettera sottolinea che partecipare alla revisione non equivale a un avallo. Al momento della stesura dell’articolo, nessuno aveva pubblicamente trovato un errore.
Williams ha detto che parti della dimostrazione di OpenAI sembrano di routine, mentre "due o tre parti dall’aspetto alieno" necessitano ancora di scrutinio. Impagliazzo, uno degli autori dell’ETH, ha descritto il risultato come profondamente sorprendente.
Cosa cambia e cosa no
In pratica, oggi non cambia quasi nulla (fiù): i nuovi algoritmi battono il brute force solo su input molto più grandi di quanto un computer potrà mai contenere.
Niente solver SAT più veloci
L’articolo di Anthropic afferma che il suo metodo supera il brute force solo su input astronomicamente grandi. Per formule tipiche con cinque clausole per variabile, il punto di incrocio è un numero con circa 10.000 cifre. Nel caso più generale, è un numero con all’incirca 100 milioni di cifre.
Gli autori affermano anche che il loro approccio è improbabile che aiuti su qualsiasi cosa al di sotto di circa 10 milioni di variabili. I solver SAT usati nella verifica dei chip, nella schedulazione e nella pianificazione non diventeranno più veloci grazie a questo risultato.
La crittografia non è compromessa
Il risultato non tocca P vs NP. Nessuno lo sostiene. OpenAI dice di aver verificato se l’algoritmo rompe sistemi crittografici reali ed è abbastanza fiduciosa che non lo faccia.
La teoria si riscrive
L’impatto maggiore è sulla ricerca. I risultati di durezza basati su ETH o SETH ora necessitano di nuovi fondamenti, e alcuni ricercatori hanno detto che anni del proprio lavoro potrebbero dover essere rivisti. Non cade tutto, però. Anthropic nota che il risultato non confuta il problema dei vettori ortogonali, che supporta molti risultati di complessità fine-grained.
Perché è importante per l’AI
Il punto non è tanto 3-SAT quanto chi ha trovato la risposta: due sistemi di AI hanno indipendentemente ribaltato una congettura a cui gli esperti umani si affidavano da una generazione.
L’AI come collaboratore di ricerca
I ricercatori descrivono ormai nuovi risultati di AI che arrivano ogni una o due settimane, sconvolgendo progetti già in corso. Strumenti formali come Lean stanno diventando centrali perché permettono agli umani di fidarsi di una lunga dimostrazione scritta da una macchina senza doverla ri-derivare riga per riga.
Scorciatoie nascoste e auto-miglioramento
L’ETH sintetizzava la convinzione che alcuni problemi di ricerca non avessero scorciatoie intelligenti. Se questa convinzione è sbagliata, anche altri problemi apparentemente duri potrebbero nascondere scorciatoie.
Penso alla scoperta di algoritmi come un’area in cui tali scorciatoie potrebbero contare molto per il miglioramento ricorsivo, l’idea di sistemi di AI che aiutano a progettare AI migliori. Usare l’AI per trovare algoritmi più veloci è un percorso concreto in quella direzione, anche se nulla in questo risultato lo realizza direttamente oggi.
Cosa significa per chi lavora con i dati
Per chi costruisce con i dati, emergono tre lezioni:
Conclusione
Se le dimostrazioni supereranno la revisione degli esperti, l’ipotesi del tempo esponenziale entrerà nel breve elenco di congetture ampiamente credute che si sono rivelate false (come la congettura sulla somma di potenze di Eulero). Ma P vs NP resta aperto e la crittografia è al sicuro per ora.
I prossimi traguardi da seguire sono i workshop di revisione guidati dagli autori originali dell’ETH, reimplementazioni indipendenti degli algoritmi e l’eventuale ulteriore affinamento del limite.
Per costruire le basi dietro storie come questa, esplora i nostri corsi su strutture dati e algoritmi, programmazione in Python e machine learning. Coprono il pensiero Big-O che rende leggibili risultati come questo.