Ipotesi del tempo esponenziale (ETH)

Alcuni problemi sappiamo risolverli solo provando quasi tutte le possibilità. L’ipotesi del tempo esponenziale, in inglese Exponential Time Hypothesis e in breve ETH, è la scommessa degli informatici che, per un problema ben preciso, non ci sia altro modo, per quanto possiamo essere bravi. Esistono metodi più veloci, ma anche i migliori avranno bisogno di un numero di passi che cresce esponenzialmente con la dimensione del problema.

L’ETH è strettamente legata al problema P contro NP, a cui abbiamo dedicato un articolo a parte. Se non l’hai letto, dacci prima un’occhiata, perché ci costruiremo sopra. Soprattutto su che cos’è la complessità di un algoritmo e sul perché tra n² e 2ⁿ ci sia un abisso così grande.

Chi invitare alla festa

Stai organizzando una festa e vuoi invitare quattro amici: Tommaso, Jacopo, Katia e Davide. Il guaio è che tra di loro ci sono rapporti di ogni tipo e vorresti che fossero tutti contenti. Dopo averli interrogati a lungo, ti vengono fuori sei condizioni:

1. Viene Tommaso oppure Katia (anche tutti e due).
2. Jacopo e Katia non si sopportano, quindi non vengono tutti e due.
3. Davide viene solo se viene anche Jacopo.
4. Se viene Tommaso, deve venire anche Katia oppure Davide.
5. Se vengono sia Tommaso sia Katia, deve venire anche Jacopo.
6. Viene almeno uno dei tre: Tommaso, Jacopo, Davide.

Chi devi invitare perché valgano tutte le condizioni contemporaneamente? Prova a scoprirlo da solo: la soluzione è alla fine dell’articolo.

Un informatico riscriverebbe il problema nel linguaggio della logica proposizionale. Ogni amico riceve una lettera, per esempio T come Tommaso. La lettera è vera (Tommaso viene) oppure falsa (Tommaso non viene). Il simbolo ∨ si legge «o» e ¬ si legge «non». La prima condizione diventa allora:

$$T\vee K$$

La seconda condizione dice che non viene Jacopo oppure non viene Katia:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Con la terza condizione è facile sbagliare. «Davide viene solo se viene anche Jacopo» significa che non deve succedere che Davide venga e Jacopo no. Quindi o Davide non viene, oppure viene Jacopo:

$$\mathrm{\neg }D\vee J$$

Allo stesso modo riscriviamo anche il resto. L’intero problema diventa:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Osserva quanto si somigliano le condizioni: qualche lettera, alcune con il segno ¬, unite dalla parola «o». E nessuna ha più di tre lettere. Il problema in cui abbiamo condizioni di questo tipo e cerchiamo come assegnare alle lettere vero e falso in modo che valgano tutte insieme si chiama 3-SAT. Il tre indica che ogni condizione ha al massimo tre lettere, e SAT è l’abbreviazione dell’inglese satisfiability, soddisfacibilità.

A prima vista sembra un giochino da settimana enigmistica. Eppure un’enorme quantità di problemi pratici si può riscrivere nella forma 3-SAT: l’orario delle lezioni, la verifica che un chip di un processore calcoli correttamente, la pianificazione dei turni e perfino il sudoku. Allora le lettere non sono quattro, ma tranquillamente milioni.

Quante possibilità bisogna provare?

Il metodo più diretto è provare tutto. Tommaso viene o non viene: sono due possibilità. Per ciascuna di esse Jacopo viene o non viene: sono già quattro possibilità. Per quattro amici sono

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

È lo stesso ragionamento che abbiamo fatto con i vettori binari nell’articolo su P contro NP. Se abbiamo n lettere, possiamo assegnare loro vero e falso in 2ⁿ modi. Per 4 amici sono 16 possibilità, che controlli in pochi minuti. Per 100 lettere sono

$$2^{100}\approx 1,27\cdot {10}^{30}$$

possibilità. Se un computer provasse un miliardo di possibilità al secondo, gli servirebbe circa tremila volte il tempo trascorso da quando esiste l’universo.

Al contrario, invece, è facile: se qualcuno ti dice «invita questi tre», lo verifichi subito. Basta passare in rassegna le sei condizioni e guardare se ciascuna vale. Trovare la soluzione è difficile, controllarla è facile. Proprio problemi di questo tipo, nell’articolo su P contro NP, li abbiamo messi nella classe NP.

Però 3-SAT non è un problema qualsiasi di NP: nel 1971 si è dimostrato che in 3-SAT si può tradurre qualsiasi problema di NP. Chi sapesse risolvere 3-SAT velocemente, quindi, saprebbe risolvere velocemente proprio tutto ciò che si può verificare velocemente. I problemi con questa proprietà si chiamano NP-completi e 3-SAT ne è il rappresentante più famoso.

Si può fare meglio di 2ⁿ?

Sì. Provare proprio tutto è inutile. Basta accorgersi, per esempio, che se Tommaso non viene, dalla prima condizione segue subito che deve venire Katia. Tutte le possibilità in cui non verrebbe nessuno dei due le scartiamo direttamente. Gli algoritmi intelligenti combinano tutta una serie di trucchi di questo tipo. I migliori oggi conosciuti richiedono circa

$${\mathrm{1,307}}^n$$

passi. È un salto enorme. Per n = 100, invece di 10³⁰ si ottengono circa 4,2 · 10¹¹ passi, che un computer esegue in pochi minuti.

Ma attenzione, c’è il tranello. 1,307ⁿ è pur sempre una funzione esponenziale. Abbiamo ridotto la base da due a 1,307, ma la variabile n è rimasta all’esponente. Se n continua a crescere, alla fine ci schiaccerà comunque. Per n = 1000 anche 1,307ⁿ è un numero di 117 cifre.

E come sarebbe un algoritmo che non è esponenziale? Per esempio uno che se la cava con n³ passi. Sarebbe polinomiale e 3-SAT apparterrebbe allora alla classe P. Tra i polinomi e gli esponenziali, però, c’è ancora una zona grigia: funzioni che crescono più velocemente di qualsiasi polinomio e tuttavia più lentamente di qualsiasi esponenziale. Per esempio

$$2^{\sqrt{n}}.$$

Qui all’esponente c’è solo la radice quadrata di n. Confrontiamo le quattro funzioni in una tabella:

Per n = 1000, $2^{\sqrt{n}}$ gioca nello stesso campionato di n³, mentre i due esponenziali sono schizzati verso numeri per cui non abbiamo nemmeno un nome. Le funzioni come $2^{\sqrt{n}}$, che crescono più lentamente di cⁿ per qualsiasi base c maggiore di uno, si chiamano subesponenziali.

La stessa cosa la mostra il grafico. L’asse verticale è logaritmico: ogni tacca verso l’alto significa un numero centomila volte più grande. Altrimenti nella figura non ci starebbe nient’altro che 2ⁿ.

In un grafico così gli esponenziali sono rette che salgono sempre. La rossa 2ⁿ è più ripida dell’arancione 1,307ⁿ, ma sono entrambe rette. È interessante che l’arancione all’inizio stia addirittura sotto la verde n³. La sorpassa solo intorno a n = 42, ma da lì in poi per sempre. La blu $2^{\sqrt{n}}$, invece, si piega e resta in basso vicino alla verde.

Che cosa afferma esattamente l’ETH

Ora possiamo finalmente enunciare l’ipotesi. L’hanno formulata nel 1999 Russell Impagliazzo e Ramamohan Paturi:

Esiste un numero c maggiore di uno tale che nessun algoritmo può risolvere 3-SAT con n lettere più velocemente che in circa cⁿ passi.

E in parole povere? La base dell’esponenziale sappiamo ridurla con trucchi ingegnosi: da due a 1,5, a 1,307, forse un giorno a 1,2. Ma non riusciremo mai ad avvicinarla a uno quanto vogliamo. Da qualche parte c’è un limite sotto il quale non si può scendere. Secondo l’ETH, quindi, un algoritmo di complessità $2^{\sqrt{n}}$ non dovrebbe esistere.

Perché ipotesi? Perché nessuno la sa dimostrare. L’ETH è un’assunzione di lavoro, un po’ come nell’articolo su P contro NP assumiamo che P ≠ NP. La maggior parte degli informatici ci crede, perché decenni di sforzi hanno portato solo a far scendere lentamente la base a partire dal due. Ma una dimostrazione non ce l’ha in mano nessuno.

L’ETH e P contro NP

Che legame c’è tra queste due domande? Immagina che 3-SAT abbia una difficoltà «vera», cioè l’algoritmo più veloce possibile. Questo può stare in tre fasce:

• Fascia verde, polinomiale. 3-SAT si può risolvere per esempio in n³ passi. Dato che 3-SAT è NP-completo, varrebbe allora P = NP e l’ETH ovviamente non varrebbe.
• Fascia blu, subesponenziale. 3-SAT si può risolvere in $2^{\sqrt{n}}$ passi o qualcosa di simile. In tempo polinomiale no, quindi vale P ≠ NP. Ma l’ETH non varrebbe.
• Fascia rossa, esponenziale. Meglio di cⁿ non si può fare. L’ETH vale e di conseguenza vale anche P ≠ NP.

Dalla figura si vede che l’ETH è un’affermazione più forte di P ≠ NP. Non dice soltanto che 3-SAT non si può risolvere in tempo polinomiale, ma che non si può risolvere nemmeno in tempo subesponenziale. Chi dimostrasse l’ETH dimostrerebbe con questo anche P ≠ NP e vincerebbe un milione di dollari.

E al contrario: chi confutasse l’ETH non avrebbe per questo ancora dimostrato P = NP. Gli basta un algoritmo della fascia blu. Tienilo a mente, tra poco ci servirà.

A che cosa serve l’ETH

Dimostrare che un problema non si può risolvere velocemente è, in informatica, incredibilmente difficile. Non sappiamo farlo quasi mai. L’ETH ci offre una scappatoia: invece di «il problema X è difficile» dimostriamo «il problema X è difficile se vale l’ETH».

Come? Mostriamo che, se il problema X si potesse risolvere velocemente, si potrebbe risolvere velocemente anche 3-SAT. Prendiamo per esempio questo: abbiamo n persone e di alcune coppie sappiamo che non si sopportano. Vogliamo distribuirle in tre stanze in modo che nessuna di queste coppie finisca nella stessa stanza. Gli informatici lo chiamano colorazione di un grafo con tre colori. Da ogni problema 3-SAT lo si può costruire in modo che il numero di persone sia solo un piccolo multiplo del numero di lettere. Se quindi si potessero distribuire le persone nelle stanze in tempo subesponenziale, si potrebbe risolvere in tempo subesponenziale anche 3-SAT e l’ETH cadrebbe.

Di risultati condizionali come questo oggi ce ne sono centinaia. Un intero settore, che studia quanto sono esattamente difficili i singoli problemi, poggia sull’ETH come una casa sulle fondamenta.

L’ETH ha anche una sorella più forte, l’ipotesi forte del tempo esponenziale (SETH). Questa si concentra sui problemi in cui le condizioni possono avere più di tre lettere, per esempio dieci o cento. La SETH afferma che quanto più lunghe sono le condizioni che ammettiamo, tanto più la migliore base possibile si avvicina a due. Per condizioni lunghe, quindi, non si potrebbe risparmiare quasi nulla rispetto a provare alla cieca tutte le 2ⁿ possibilità.

Perché ora si parla dell’ETH

L’azienda OpenAI, che conosci soprattutto per ChatGPT, a ottobre 2026 ha pubblicato un preprint, cioè un articolo che non è ancora passato attraverso la revisione paritaria. Si intitola The Exponential Time Hypothesis is False, in italiano «L’ipotesi del tempo esponenziale è falsa». In esso OpenAI afferma di aver trovato un algoritmo che risolve 3-SAT in circa

$$2^{\frac{n}{\sqrt{\ln n}}}$$

passi. All’esponente, quindi, non c’è n da sola, ma n divisa per la radice quadrata del logaritmo (naturale). Quel denominatore cresce terribilmente piano, ma cresce, e questo basta perché la funzione sia subesponenziale. L’algoritmo, a quanto pare, sa addirittura non solo trovare una soluzione, ma anche contare quante soluzioni esistono.

Se fosse vero, l’algoritmo di OpenAI cadrebbe nella fascia blu della figura qui sopra. E che cosa significherebbe?

• L’ETH cadrebbe e con lei anche la SETH e le centinaia di risultati condizionali che si reggevano su di esse. Gli informatici dovrebbero buttare via o riscrivere un sacco di «se vale l’ETH, allora…».
• Il problema P contro NP non sarebbe risolto. L’algoritmo continua a non essere polinomiale.
• In pratica non cambierebbe quasi nulla. Nella formula si nascondono costanti che non conosciamo. Se fossero uguali a uno, per n = 1000 si avrebbe $\sqrt{\ln n}$ circa uguale a 2,6 e otterremmo circa 2³⁸⁰ passi. È quasi lo stesso di 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ dei migliori algoritmi di oggi. Il nuovo algoritmo supererebbe nettamente quelli attuali solo per n ancora più grandi, e di quanto dipende proprio dalle costanti sconosciute. Ha quindi soprattutto un significato teorico. La crittografia e le banche non ne sono toccate.

Per ora si tratta di un’affermazione non verificata. La dimostrazione è lunga e tecnica e gli esperti stanno appena cominciando a leggerla. In passato i grandi annunci di problemi risolti si sono già rivelati errati molte volte, quindi per ora vale una regola: aspettiamo di sentire che cosa ne dicono gli esperti. Questo paragrafo lo scriviamo il 27 ottobre 2026.

Soluzione del problema della festa

Devi invitare Tommaso, Jacopo e Davide, Katia no. Nella figura ci sono tutte le 16 possibilità. In ogni colonna c’è una possibilità: il cerchietto pieno significa che l’amico viene, quello vuoto che non viene. Il numero rosso sotto la colonna indica la prima condizione che non vale. L’unica possibilità in cui valgono tutte le condizioni è incorniciata in verde.

Ed ecco proprio la forza bruta che l’ETH considera quasi insuperabile: per quattro amici sedici colonne, per cento amici più colonne di quanti atomi ci siano nel nostro corpo.

Vedi anche

• Il più grande problema dell’informatica: P contro NP
• Logica proposizionale
• Funzione esponenziale
• Crescita esponenziale