Il 26 ottobre 2026 OpenAI ha annunciato tre risultati prodotti dai suoi modelli interni. Il più rilevante per chi lavora con il software è un algoritmo che, se la verifica in corso lo confermerà, confuta l’Exponential Time Hypothesis (ETH), una delle ipotesi su cui si regge da oltre venticinque anni buona parte della complessità computazionale. È il seguito del rilascio del 6 ottobre, di cui avevo scritto in È davvero finito il mondo che conoscevamo?.

P, NP e il posto dell’ETH

P è la classe dei problemi che un algoritmo risolve in tempo polinomiale, con un numero di passi che cresce come una potenza della dimensione dell’input (n2, n3…). NP è la classe dei problemi in cui una soluzione proposta si controlla in tempo polinomiale, anche se trovarla può richiedere molto di più.

L’esempio di riferimento è SAT (satisfiability). Date n variabili che valgono vero o falso, combinate con «e», «o» e «non» come in (x₁ o non x₂) e (x₂ o x₃), ci si chiede se esiste un’assegnazione che renda vera la formula. Controllarne una è immediato, trovarla può voler dire provare 2n combinazioni, più di 1030 con cento variabili. Nella versione 3-SAT, con tre variabili per parentesi, il problema è NP-completo: ogni problema di NP vi si può tradurre, quindi un algoritmo polinomiale per 3-SAT darebbe P = NP.

L’ETH, formulata fra il 1999 e il 2001 da Russell Impagliazzo, Ramamohan Paturi e Francis Zane, va oltre P ≠ NP: afferma che 3-SAT richiede nel caso peggiore un tempo esponenziale, 2Ω(n). Non è mai stata dimostrata, ma insieme alla sua versione forte, la SETH, è diventata la base di centinaia di limiti di difficoltà nella complessità fine-grained, quella che si chiede quale esponente esatto serva a un problema.

Il nuovo risultato

Il paper presenta un algoritmo deterministico che conta le soluzioni di qualunque formula k-CNF con n variabili in tempo 2O(n log log n / √log n) a meno di fattori polinomiali, cioè subesponenziale. La tecnica è algebrica: la formula diventa un polinomio e il conteggio si riduce agli zeri comuni di sistemi di equazioni polinomiali sparse. Il modello ha prodotto la confutazione il 16 ottobre e la formalizzazione in Lean il 17. Paper e dimostrazione sono pubblici e la verifica è affidata a un gruppo guidato da Impagliazzo, Paturi e Ryan Williams.

Se il teorema regge, cadono ETH e SETH. P contro NP resta aperto, perché 2n/√log n cresce comunque più di qualunque polinomio. Molti limiti fine-grained perdono una base ma non tutte, perché diversi seguono anche da ipotesi più deboli come la Orthogonal Vectors Conjecture. Le costanti nascoste non sono note e OpenAI stessa scrive che per ricadute pratiche servirà molta ricerca.

Gli altri due risultati sono la dimostrazione in ogni dimensione della congettura di local smoothing di Christopher Sogge e l’esistenza rigorosa della cromodinamica quantistica e della teoria di Yang-Mills pura, senza il mass gap richiesto dal problema del millennio.

Cosa ne penso

L’AI sta confermando una cosa che non riuscivamo a vedere bene: i fenomeni esponenziali restano difficili da comprendere per le persone. Vale per la crescita dell’AI stessa: secondo METR la durata dei compiti che i modelli completano da soli raddoppia circa ogni sette mesi. Se la tendenza continuasse, in cinque anni sarebbero otto raddoppi e mezzo, un fattore di quasi 400. Vale per le pandemie e per i fenomeni virali. E vale per l’ETH: se il risultato regge, per oltre venticinque anni il confine fra esponenziale e subesponenziale in uno dei problemi più studiati dell’informatica è stato collocato nel posto sbagliato.

La difficoltà è misurata. Nel 1975 Wagenaar e Sagaria hanno osservato che spesso due terzi dei partecipanti stimavano una crescita esponenziale sotto il 10% del valore corretto. Nel 2020 Lammers, Crusius e Gast hanno trovato lo stesso errore sui contagi da coronavirus: le persone immaginavano una crescita lineare. Secondo Stanislas Dehaene l’intuizione spontanea dei numeri è logaritmica e la scala lineare si impara a scuola.

Il caso dell’ETH mostra che il confine è difficile da vedere anche per chi lo studia di mestiere. A titolo indicativo, con logaritmi in base 2 e ignorando le costanti, per una formula con un milione di variabili l’esponente del nuovo algoritmo vale ancora circa n, come quello della ricerca esaustiva. Per dimezzarlo servono circa 1077 variabili, un numero vicino a quello degli atomi dell’universo osservabile. Esponenziale e subesponenziale si separano a scale che nessuna esperienza diretta raggiunge. Lì l’intuizione non arriva e servono le dimostrazioni.

Eppure siamo il prodotto di fasi di crescita molto rapide, come l’esplosione del Cambriano e le altre radiazioni evolutive che hanno moltiplicato le forme di vita in tempi brevi su scala geologica. La teoria degli equilibri punteggiati di Niles Eldredge e Stephen Jay Gould, ancora discussa, descrive l’evoluzione come lunghi periodi di stabilità interrotti da brevi accelerazioni. Avvengono però su scale di milioni di anni, mentre la nostra intuizione è tarata sul tempo di una vita, anzi spesso di giorni.

Se l’intuizione non basta, servono strumenti che la estendano. Misure ripetute come quelle di METR rendono visibile una crescita prima che diventi evidente. Una dimostrazione in Lean permette di verificare che un algoritmo subesponenziale esiste anche quando l’intuizione non lo vede. Credo che sia questo il ruolo della parte umana in una superintelligenza governata: stabilire che cosa conta, verificare e rispondere dei risultati.

Immagine di copertina: conchiglia di nautilo in sezione. Ogni nuova camera è più grande della precedente nella stessa proporzione e insieme disegnano una spirale logaritmica: una crescita esponenziale prodotta dall’evoluzione. Foto di Chris 73 su Wikimedia Commons — CC BY-SA 3.0 — https://commons.wikimedia.org/wiki/File:NautilusCutawayLogarithmicSpiral.jpg — licenza: https://creativecommons.org/licenses/by-sa/3.0/