Avete presente quando passate ore a debuggare un pezzo di codice convinti che la logica sia impeccabile, per poi scoprire che il problema era un semplice errore di sintassi o un punto e virgola dimenticato? Ecco, la teoria della complessità computazionale sta vivendo esattamente questo momento di crisi esistenziale.
Il titolo del paper è piuttosto brutale, quasi un insulto alla matematica classica: «The Exponential Time Hypothesis Is False». Per chi non ha passato le notti insonni su libri di algoritmi, la ETH (Exponential Time Hypothesis) è quel presupposto (non ancora dimostrato, ma accettato come verità sacra) secondo cui certi problemi sono intrinsecamente difficili e richiedono tempi di calcolo esponenziali per essere risolti. È il muro contro cui si scontrano i nostri tentativi di ottimizzazione.
Ma qualcuno, molto probabilmente tra i laboratori di OpenAI che non si accontentano di addestrare chatbot che scrivono poesie d’amore sfigate, ha deciso di scoperchiare il vaso di Pandora. Il paper suggerisce che questo muro potrebbe non esistere affatto. Se la ETH cade, crollano con essa un sacco di assunzioni su quanto siano ‘difficili’ i problemi di ricerca e ottimizzazione. Non è solo una questione di accademici che si scambiano sguardi torvi durante i conferenze; è un cambio di paradigma che potrebbe rendere risolvibili problemi che oggi consideriamo impossibili.
Certo, restiamo con i piedi per terra. Siamo in Italia, dove spesso la ricerca riceve briciole rispetto ai giganti della Silicon Valley, e leggere una notizia che arriva direttamente dai repository di OpenAI ci fa sentire un po’ come gli spettatori di una serie sci-fi che guardano l’invasione aliena dalla finestra di un bar a Trastevere. Però, il contenuto è di una potenza devastante. Se l’ipotesi è falsa, la nostra mappa del territorio computazionale è profondamente errata.
Non stiamo parlando di un aggiornamento software che velocizza il boot di Windows. Stiamo parlando di ridefinire i limiti di ciò che è calcolabile in tempi umani. Se riuscissimo a trovare algoritmi super-efficienti dove prima vedevamo solo muri di complessità esponenziale, le implicazioni per la crittografia, l’ottimizzazione logistica e l’IA sarebbero sbalorditive.
C’è da stare con le orecchie tese. Se questo paper regge l’urto della peer-review, preparatevi: il mondo dell’informatica sta per subire un reboot totale. E speriamo bene che, stavolta, non ci sia un sistema di abbonamento mensile per accedere ai nuovi algoritmi velocizzati.