Per quasi tre decenni, un’ipotesi nota come Exponential Time Hypothesis è rimasta silenziosamente alla base dell’informatica teorica. Non una legge, non un teorema, ma un’assunto così ampiamente accettato che interi campi di ricerca sono stati edificati sopra di esso. OpenAI sostiene ora che i suoi modelli di IA abbiano prodotto un algoritmo che la smentisce. Se la scoperta verrà confermata, le conseguenze andranno ben oltre un singolo articolo di ricerca.
Cosa diceva realmente la Exponential Time Hypothesis
La Exponential Time Hypothesis, proposta circa 30 anni fa, affronta una domanda apparentemente semplice: quanto velocemente un computer può risolvere determinati problemi logici? L’approccio più diretto è la forza bruta, testando ogni possibile combinazione di vero o falso per ciascuna variabile del problema. La ETH non sosteneva che questo fosse l’unico modo. Riconosceva che esistono delle scorciatoie. Ciò che proponeva era un limite inferiore, cioè che, per quanto intelligente sia la scorciatoia, il lavoro computazionale richiesto debba comunque crescere in modo esponenziale man mano che il problema diventa più grande.
Questo suona tecnico, ma la conseguenza pratica è significativa. La ETH era essenzialmente un limite di velocità su una classe di problemi. Diceva ai ricercatori cosa era, in linea di principio, ottenibile e cosa no. Interi rami di algoritmi e teoria della complessità sono stati sviluppati dando quel limite per scontato.
OpenAI afferma che i suoi modelli hanno ideato un algoritmo che batte quel presunto limite di velocità. L’affermazione è che la ETH è falsa.
L’effetto a catena: cosa si rompe quando un fondamento si sposta
Questo è ciò che la maggior parte della copertura mediatica sull’annuncio si perde. La storia non riguarda solo un’ipotesi che si rivela errata. Riguarda ciò che è stato costruito sopra di essa.
Fedor Fomin dell’Università di Bergen descrive la reazione tra i ricercatori come uno shock totale. Nota che un libro di testo che ha scritto sull’argomento diventerebbe obsoleto se la scoperta fosse confermata. Non è iperbole. Molte conclusioni dell’informatica sono state ricavate assumendo che la ETH fosse vera. Se l’assunto cade, quelle conclusioni non reggono più. Come dice Fomin, il risultato richiederebbe una revisione completa di diversi settori degli algoritmi e della complessità.
Leslie Goldberg dell’Università di Oxford la definisce, a determinate condizioni, una svolta enorme. La condizione è importante: la scoperta deve ancora essere verificata e, aspetto cruciale, compresa. Stefan Szeider della TU Wien ha esaminato ciò che OpenAI ha pubblicato e si aspetta che superi il vaglio della verifica, ma nota che i ricercatori devono ancora confermare che l’enunciato formalmente dimostrato significhi ciò che i suoi autori dicono che significhi. Quella distinzione, tra una prova tecnicamente valida e una prova che significa ciò che pensi che significhi, non è di poco conto.
La ETH è anche collegata a uno dei problemi aperti più famosi della matematica: P versus NP. Questo riguarda la questione se i problemi le cui risposte sono facili da verificare siano anche facili da risolvere. Il fatto che la ETH fosse vera avrebbe implicato che la risposta è no. Ma Goldberg è esplicito: smentire la ETH non significa che la risposta sia sì. La questione P versus NP rimane aperta.
OpenAI ha usato Lean, uno strumento software che verifica formalmente le prove matematiche, per controllare il risultato sulla ETH. Ha anche incaricato un gruppo di revisione indipendente che include Russell Impagliazzo e Ramamohan Paturi, entrambi dell’Università della California a San Diego, tra i ricercatori che avevano originariamente proposto la ETH. La loro lettera aperta descrive la scoperta come qualcosa che potrebbe cambiare una parte importante dell’informatica teorica.
Matematica fatta tramite comunicati stampa, e perché questa frase è importante
Il risultato sulla ETH non è stato l’unico annuncio. OpenAI sostiene anche che la sua IA ha dimostrato una congettura del 1991 sul comportamento delle onde, con implicazioni per il modo in cui le onde si propagano e per quanto una forma possa essere sottile pur contenendo ancora segmenti di linea che puntano in ogni direzione. Nella fisica teorica, sostiene di aver dimostrato che le teorie quantistiche dei campi, inclusa la cromodinamica quantistica, che descrive la forza forte che tiene insieme i quark, sono matematicamente coerenti anziché solo utili dal punto di vista sperimentale. Il lavoro che tocca l’esistenza della pura teoria di Yang-Mills, parte di un problema matematico da un milione di dollari, non è stato reso pubblico mentre un gruppo guidato dal premio Nobel David Gross lo esamina.
La portata di questi annunci ha generato disagio negli ambienti accademici. Magnus Wahlström della Royal Holloway dell’Università di Londra descrive il fenomeno come “matematica fatta tramite comunicati stampa”, sollevando il timore che modelli di IA proprietari possano ribaltare improvvisamente mesi di lavoro dei ricercatori senza il solito processo di revisione paritaria e verifica graduale.
Clément Canonne dell’Università di Sydney traccia una netta distinzione che vale la pena tenere a mente: dimostrare qualcosa e capire perché è vero non sono la stessa cosa. La rete di scoperte che si basava sulla ETH è crollata. Il motivo per cui è crollata rimane sconosciuto.
In breve
Un’ipotesi che ha plasmato l’informatica teorica per 30 anni potrebbe essere stata smentita da un modello di IA. Se confermate, le implicazioni sono strutturali: le conclusioni basate sulla ETH in tutti gli algoritmi e nella teoria della complessità andrebbero riviste. La scoperta è al vaglio di una revisione indipendente, anche da parte dei ricercatori che avevano originariamente proposto l’ipotesi. Ciò che rende questo momento davvero insolito non è solo il risultato in sé, ma il divario che rivela: i sistemi di IA possono ora produrre prove che gli umani non sanno ancora spiegare fino in fondo. Quel divario tra prova e comprensione è il luogo in cui inizia il vero lavoro.
Basato su un articolo di New Scientist.