Per gli algoritmi, la memoria è una risorsa molto più potente del tempo

La versione originale di questa storia è apparsa su Quanta Magazine .

Un pomeriggio di luglio del 2024, Ryan Williams decise di dimostrare di essersi sbagliato. Erano passati due mesi da quando aveva fatto una scoperta sorprendente sul rapporto tra tempo e memoria nell'informatica. Si trattava di un abbozzo di una dimostrazione matematica del fatto che la memoria fosse più potente di quanto gli informatici credessero: una piccola quantità di tempo sarebbe stata utile quanto molto tempo in tutti i calcoli immaginabili. Sembrava così improbabile che pensò che qualcosa dovesse andare storto, e mise subito da parte la dimostrazione per concentrarsi su idee meno folli. Ora, finalmente, si era ritagliato il tempo per trovare l'errore.

Non è andata così. Dopo ore passate a studiare attentamente la sua argomentazione, Williams non è riuscito a trovare una sola falla.

"Pensavo solo di stare impazzendo", ha detto Williams, informatico teorico del Massachusetts Institute of Technology. Per la prima volta, ha iniziato a considerare la possibilità che forse, solo forse, la memoria fosse davvero così potente come suggeriva il suo lavoro.

Nei mesi successivi, ha approfondito i dettagli, ha esaminato attentamente ogni passaggio e ha chiesto il feedback di una manciata di altri ricercatori. A febbraio, ha finalmente pubblicato la sua dimostrazione online , riscuotendo un ampio consenso.

"È incredibile. È bellissimo", ha detto Avi Wigderson , informatico teorico presso l'Institute for Advanced Study di Princeton, nel New Jersey. Non appena ha saputo la notizia, Wigderson ha inviato a Williams un'email di congratulazioni. L'oggetto era: "Mi hai lasciato senza parole".

Tempo e memoria (chiamata anche spazio) sono le due risorse più fondamentali del calcolo: ogni algoritmo richiede un certo tempo per essere eseguito e un certo spazio per memorizzare i dati durante l'esecuzione. Finora, gli unici algoritmi noti per svolgere determinati compiti richiedevano una quantità di spazio approssimativamente proporzionale al loro tempo di esecuzione, e i ricercatori avevano a lungo ipotizzato che non ci fosse modo di fare di meglio. La dimostrazione di Williams ha stabilito una procedura matematica per trasformare qualsiasi algoritmo, indipendentemente da ciò che fa, in una forma che utilizza molto meno spazio.

Inoltre, questo risultato – un'affermazione su ciò che è possibile calcolare data una certa quantità di spazio – implica anche un secondo risultato, su ciò che non è possibile calcolare in un certo lasso di tempo. Questo secondo risultato non è sorprendente di per sé: i ricercatori si aspettavano che fosse vero, ma non avevano idea di come dimostrarlo. La soluzione di Williams, basata sul suo primo risultato schiacciante, sembra quasi esagerata, quasi da cartone animato, simile a dimostrare la colpevolezza di un presunto assassino fornendo un alibi di ferro per tutti gli altri sul pianeta. Potrebbe anche offrire un nuovo modo di affrontare uno dei più antichi problemi aperti dell'informatica.

"È un risultato davvero sorprendente e un enorme passo avanti", ha affermato Paul Beame , informatico dell'Università di Washington. "È un po' meno sorprendente che sia Ryan a farlo."

Williams, 46 anni, ha un viso aperto ed espressivo e un accenno di grigio tra i capelli. Il suo ufficio, che si affaccia sulle guglie colorate dello Stata Center del MIT, è un'altra dimostrazione dell'uso creativo dello spazio. Un paio di tappetini da yoga hanno trasformato il davanzale di una finestra in un angolo di lettura improvvisato, e la scrivania è incastrata in un angolo dalla forma strana, liberando spazio per un divano di fronte a una grande lavagna bianca piena di scarabocchi matematici.

Il MIT è molto lontano dalla casa d'infanzia di Williams, nell'Alabama rurale, dove lo spazio non mancava. È cresciuto in una fattoria di 50 acri e ha visto un computer per la prima volta a 7 anni, quando sua madre lo ha accompagnato in macchina attraverso la contea per un corso speciale di arricchimento accademico. Ricordava di essere rimasto affascinato da un semplice programma per generare uno spettacolo pirotecnico digitale.

"Si trattava di prendere un colore a caso e di inviarlo in una direzione casuale dal centro del monitor", ha detto Williams. "Non si poteva prevedere quale immagine si sarebbe ottenuta". Il mondo dei computer sembrava un parco giochi selvaggio e meraviglioso, pieno di infinite possibilità. Il giovane Williams ne era affascinato.

"Scrivevo programmi per me stesso, su carta, da eseguire su un computer futuro", ha detto. "I miei genitori non sapevano davvero cosa farsene di me".

Crescendo, Williams passò dai computer immaginari a quelli reali. Per gli ultimi due anni di liceo, si trasferì all'Alabama School of Math and Science, un prestigioso collegio pubblico, dove incontrò per la prima volta il lato teorico dell'informatica.

"Mi sono reso conto che esisteva un mondo più vasto di cose là fuori, e che esisteva un modo per pensare matematicamente ai computer", ha detto. "Era quello che volevo fare."

Williams era particolarmente attratto da una branca dell'informatica teorica chiamata teoria della complessità computazionale. Essa si occupa delle risorse (come tempo e spazio) necessarie per risolvere problemi computazionali come l'ordinamento di liste o la fattorizzazione di numeri. La maggior parte dei problemi può essere risolta da molti algoritmi diversi, ognuno con le proprie esigenze di tempo e spazio. I teorici della complessità classificano i problemi in categorie, chiamate classi di complessità, in base alle esigenze di risorse dei migliori algoritmi per risolverli, ovvero gli algoritmi che eseguono più velocemente o utilizzano la minore quantità di spazio.

Ma come rendere matematicamente rigoroso lo studio delle risorse computazionali? Non si andrà lontano se si cerca di analizzare il tempo e lo spazio confrontando minuti e megabyte. Per fare progressi, è necessario partire dalle definizioni corrette.

Queste definizioni emersero dal lavoro di Juris Hartmanis, un pioniere dell'informatica con esperienza nell'arrangiarsi con risorse limitate. Nacque nel 1928 in un'importante famiglia lettone, ma la sua infanzia fu sconvolta dallo scoppio della Seconda Guerra Mondiale. Le forze sovietiche di occupazione arrestarono e giustiziarono suo padre e, dopo la guerra, Hartmanis completò il liceo in un campo profughi. Proseguì gli studi universitari, dove eccelleva pur non potendo permettersi i libri di testo.

"Compensavo prendendo appunti molto dettagliati durante le lezioni", ha ricordato in un'intervista del 2009. "C'è un certo vantaggio nel [dover] improvvisare e superare le difficoltà". Hartmanis emigrò negli Stati Uniti nel 1949 e svolse una serie di lavori saltuari – costruendo macchinari agricoli, lavorando l'acciaio e persino facendo il maggiordomo – mentre studiava matematica all'Università di Kansas City. Intraprese una carriera di straordinario successo nel giovane campo dell'informatica teorica.

Nel 1960, mentre lavorava presso il laboratorio di ricerca della General Electric a Schenectady, New York, Hartmanis incontrò Richard Stearns, uno studente laureato che stava svolgendo un tirocinio estivo. In due articoli innovativi , i due stabilirono precise definizioni matematiche per il tempo e lo spazio. Queste definizioni fornirono ai ricercatori il linguaggio necessario per confrontare le due risorse e classificare i problemi in classi di complessità.

Una delle classi più importanti è quella con il modesto nome "P". In parole povere, comprende tutti i problemi che possono essere risolti in un lasso di tempo ragionevole. Una classe di complessità analoga per lo spazio è denominata "PSPACE".

La relazione tra queste due classi è una delle questioni centrali della teoria della complessità. Ogni problema in P è presente anche in PSPACE, perché gli algoritmi veloci semplicemente non hanno abbastanza tempo per riempire molto spazio nella memoria di un computer. Se fosse vero anche il contrario, le due classi sarebbero equivalenti: spazio e tempo avrebbero una potenza di calcolo comparabile. Ma i teorici della complessità sospettano che PSPACE sia una classe molto più ampia, contenente molti problemi che non sono in P. In altre parole, credono che lo spazio sia una risorsa computazionale molto più potente del tempo. Questa convinzione deriva dal fatto che gli algoritmi possono utilizzare la stessa piccola porzione di memoria più e più volte, mentre il tempo non è altrettanto clemente: una volta trascorso, non è possibile recuperarlo.

"L'intuizione è semplicissima", ha detto Williams. "Si può riutilizzare lo spazio, ma non il tempo."

Ma l'intuizione non basta per i teorici della complessità: vogliono una dimostrazione rigorosa. Per dimostrare che PSPACE è maggiore di P, i ricercatori dovrebbero dimostrare che per alcuni problemi in PSPACE, gli algoritmi veloci sono categoricamente impossibili. Da dove potrebbero iniziare?

In realtà, iniziarono alla Cornell University, dove Hartmanis si trasferì nel 1965 per dirigere il neonato dipartimento di informatica. Sotto la sua guida, il dipartimento divenne rapidamente un centro di ricerca sulla teoria della complessità e, all'inizio degli anni '70, due ricercatori, John Hopcroft e Wolfgang Paul, si proposero di stabilire un collegamento preciso tra tempo e spazio.

Hopcroft e Paul sapevano che per risolvere il problema P contro PSPACE avrebbero dovuto dimostrare che non è possibile eseguire determinati calcoli in un tempo limitato. Ma è difficile dimostrare una tesi negativa. Invece, decisero di capovolgere il problema ed esplorare cosa si può fare con uno spazio limitato. Speravano di dimostrare che gli algoritmi a cui viene assegnato un certo budget spaziale possono risolvere tutti gli stessi problemi degli algoritmi con un budget temporale leggermente maggiore. Ciò indicherebbe che lo spazio è almeno leggermente più potente del tempo: un piccolo ma necessario passo verso la dimostrazione che PSPACE è più grande di P.

Con questo obiettivo in mente, si sono rivolti a un metodo che i teorici della complessità chiamano simulazione, che consiste nel trasformare algoritmi esistenti in nuovi che risolvono gli stessi problemi, ma con quantità di spazio e tempo diverse. Per comprendere l'idea di base, immagina di avere un algoritmo veloce per ordinare alfabeticamente la tua libreria, ma che ti richiede di disporre i libri in decine di piccole pile. Potresti preferire un approccio che occupi meno spazio nel tuo appartamento, anche se richiede più tempo. Una simulazione è una procedura matematica che potresti utilizzare per ottenere un algoritmo più adatto: dagli in pasto l'originale e ti fornirà un nuovo algoritmo che risparmia spazio a scapito del tempo.

I progettisti di algoritmi hanno studiato a lungo questi compromessi spazio-temporali per compiti specifici come l'ordinamento. Ma per stabilire una relazione generale tra tempo e spazio, Hopcroft e Paul avevano bisogno di qualcosa di più completo: una procedura di simulazione salvaspazio che funzionasse per ogni algoritmo, indipendentemente dal problema che risolvesse. Si aspettavano che questa generalità avesse un costo. Una simulazione universale non può sfruttare i dettagli di alcun problema specifico, quindi probabilmente non risparmierebbe tanto spazio quanto una simulazione specializzata. Ma quando Hopcroft e Paul iniziarono il loro lavoro, non esistevano metodi universali noti per risparmiare spazio. Anche un piccolo risparmio sarebbe stato un progresso.

La svolta arrivò nel 1975, dopo che Hopcroft e Paul collaborarono con un giovane ricercatore di nome Leslie Valiant . Il trio ideò una procedura di simulazione universale che consente sempre di risparmiare un po' di spazio. Indipendentemente dall'algoritmo che si usa, se ne ottiene uno equivalente il cui budget spaziale è leggermente inferiore al budget temporale dell'algoritmo originale.

"Tutto ciò che puoi fare in così tanto tempo, puoi farlo anche in un po' meno spazio", ha detto Valiant. È stato il primo passo importante nella ricerca per collegare spazio e tempo.

Ma poi il progresso si è arrestato e i teorici della complessità hanno iniziato a sospettare di aver incontrato un ostacolo fondamentale. Il problema era proprio il carattere universale della simulazione di Hopcroft, Paul e Valiant. Mentre molti problemi possono essere risolti con molto meno spazio che tempo, alcuni intuitivamente sembravano richiedere quasi la stessa quantità di spazio del tempo. Se così fosse, simulazioni universali più efficienti in termini di spazio sarebbero impossibili. Paul e altri due ricercatori hanno presto dimostrato che sono effettivamente impossibili , a patto di fare un presupposto apparentemente ovvio: diversi blocchi di dati non possono occupare lo stesso spazio in memoria contemporaneamente.

"Tutti davano per scontato che non si potesse fare di meglio", ha detto Wigderson.

Il risultato di Paul suggeriva che risolvere il problema P contro PSPACE avrebbe richiesto l'abbandono totale della simulazione a favore di un approccio diverso, ma nessuno aveva buone idee. Il problema rimase lì per 50 anni, finché Williams non ruppe finalmente la matassa.

Per prima cosa, doveva completare l'università.

Nel 1996, arrivò il momento per Williams di fare domanda di ammissione all'università. Sapeva che studiare la teoria della complessità lo avrebbe portato lontano da casa, ma i suoi genitori gli avevano chiarito che la costa occidentale e il Canada erano fuori questione. Tra le opzioni rimanenti, Cornell si distinse per il suo ruolo di primo piano nella storia della sua disciplina preferita.

"Questo Hartmanis ha definito le classi di complessità temporale e spaziale", ha ricordato di aver pensato. "È stato importante per me."

Williams fu ammesso alla Cornell con un generoso sussidio finanziario e arrivò nell'autunno del 1997, deciso a fare tutto il necessario per diventare lui stesso un teorico della complessità. La sua determinazione colpì i suoi compagni di corso.

"Era semplicemente un super-fantastico esperto di teoria della complessità", ha detto Scott Aaronson , un informatico dell'Università del Texas ad Austin, che ha lavorato con Williams alla Cornell.

Ma al secondo anno, Williams faceva fatica a tenere il passo con corsi che privilegiavano il rigore matematico rispetto all'intuizione. Dopo aver ottenuto un voto mediocre in un corso di teoria dell'informatica, l'insegnante gli suggerì di prendere in considerazione altre carriere. Ma Williams non rinunciò al suo sogno. Raddoppiò gli sforzi e si iscrisse a un corso di teoria post-laurea, sperando che un voto stellare nel corso più difficile avrebbe fatto un figurone nella sua domanda di ammissione alla scuola di specializzazione. Il professore che insegnava quel corso post-laurea era Hartmanis, all'epoca un esperto del settore.

Williams iniziò a frequentare Hartmanis ogni settimana, dove era quasi sempre l'unico studente a presentarsi. La sua tenacia diede i suoi frutti: ottenne una A nel corso e Hartmanis accettò di consigliarlo su un progetto di ricerca indipendente il semestre successivo. I loro incontri settimanali continuarono per tutta la durata del college di Williams. Hartmanis lo incoraggiò a coltivare un approccio individuale alla ricerca sulla complessità e lo allontanò con delicatezza dai vicoli ciechi.

"Allora sono stato profondamente influenzato da lui", ha detto Williams. "Credo di esserlo ancora adesso."

Ma nonostante avesse ottenuto un'ambita borsa di studio per la ricerca post-laurea dalla National Science Foundation, Williams fu respinto da tutti i programmi di dottorato a cui aveva fatto domanda. Appresa la notizia, Hartmanis telefonò a un collega, poi si voltò e si congratulò con Williams per essere stato ammesso a un master annuale alla Cornell. Un anno dopo, Williams presentò nuovamente domanda a diversi programmi di dottorato e, grazie a quell'esperienza di ricerca in più, trovò il successo.

Williams ha continuato a lavorare sulla teoria della complessità durante gli studi di specializzazione e negli anni successivi. Nel 2010, quattro anni dopo aver conseguito il dottorato, ha dimostrato un risultato fondamentale : un piccolo passo, ma il più grande degli ultimi decenni, verso la soluzione del quesito più famoso dell'informatica teorica , quello sulla natura dei problemi complessi. Quel risultato ha consolidato la reputazione di Williams, che ha continuato a scrivere decine di altri articoli su diversi argomenti della teoria della complessità.

P contro PSPACE non era uno di questi. Williams era affascinato dal problema fin da quando lo aveva incontrato per la prima volta al college. Aveva persino integrato il suo curriculum di informatica con corsi di logica e filosofia, cercando ispirazione da altre prospettive sul tempo e sullo spazio, senza successo.

"Ci ho sempre pensato", ha detto Williams. "Non riuscivo a pensare a niente di abbastanza interessante da dire al riguardo."

L'anno scorso ha finalmente trovato l'opportunità che aspettava.

La storia del nuovo risultato di Williams è iniziata con i progressi su una diversa questione relativa alla memoria nel calcolo: quali problemi possono essere risolti con uno spazio estremamente limitato? Nel 2010, il pioniere della teoria della complessità Stephen Cook e i suoi collaboratori inventarono un compito, chiamato problema di valutazione dell'albero , che dimostrarono impossibile per qualsiasi algoritmo con un budget di spazio inferiore a una soglia specifica. Ma c'era una scappatoia. La dimostrazione si basava sullo stesso presupposto di buon senso che Paul e i suoi colleghi avevano formulato decenni prima: gli algoritmi non possono memorizzare nuovi dati in uno spazio già pieno.

Per oltre un decennio, i teorici della complessità hanno cercato di colmare questa lacuna. Poi, nel 2023, il figlio di Cook, James , e un ricercatore di nome Ian Mertz l'hanno spalancata, ideando un algoritmo che ha risolto il problema della valutazione dell'albero utilizzando molto meno spazio di quanto chiunque pensasse possibile. La dimostrazione di Cook senior aveva presupposto che i bit di dati fossero come sassolini che devono occupare posizioni separate nella memoria di un algoritmo. Ma a quanto pare non è l'unico modo per archiviare i dati. "Possiamo effettivamente pensare a questi sassolini come a cose che possiamo schiacciare un po' l'una sull'altra", ha detto Beame.

L'algoritmo di Cook e Mertz ha suscitato la curiosità di molti ricercatori, ma non era chiaro se avesse applicazioni al di là del problema della valutazione degli alberi. "Nessuno si è reso conto di quanto sia centrale per la relazione tra tempo e spazio", ha detto Wigderson.

Ryan Williams fu l'eccezione. Nella primavera del 2024, un gruppo di studenti presentò l'articolo di Cook e Mertz come progetto finale in un corso da lui tenuto. Il loro entusiasmo lo spinse ad approfondire l'argomento. Non appena lo fece, gli balzò in mente un'idea. Il metodo di Cook e Mertz, si rese conto, era in realtà uno strumento multiuso per ridurre l'uso dello spazio. Perché non usarlo per alimentare una nuova simulazione universale che collegasse tempo e spazio, come quella progettata da Hopcroft, Paul e Valiant, ma migliore?

Quel risultato classico era un modo per trasformare qualsiasi algoritmo con un dato budget temporale in un nuovo algoritmo con un budget spaziale leggermente inferiore. Williams intuì che una simulazione basata su ciottoli morbidi avrebbe ridotto notevolmente l'utilizzo di spazio del nuovo algoritmo, all'incirca pari alla radice quadrata del budget temporale dell'algoritmo originale. Quel nuovo algoritmo efficiente in termini di spazio sarebbe stato anche molto più lento, quindi era improbabile che la simulazione avesse applicazioni pratiche. Ma da un punto di vista teorico, era a dir poco rivoluzionaria.

Per 50 anni, i ricercatori avevano dato per scontato che fosse impossibile migliorare la simulazione universale di Hopcroft, Paul e Valiant. L'idea di Williams, se avesse funzionato, non solo avrebbe battuto il loro record, ma lo avrebbe addirittura demolito.

"Ci ho pensato e ho pensato: 'Beh, semplicemente non può essere vero'", ha detto Williams. L'ha messo da parte e non ci è più tornato sopra fino a quel fatidico giorno di luglio, quando ha cercato di trovare la falla nell'argomentazione, senza successo. Dopo essersi reso conto che non c'era alcuna falla, ha trascorso mesi a scrivere e riscrivere la dimostrazione per renderla il più chiara possibile.

Alla fine di febbraio, Williams ha finalmente pubblicato online il documento finito . Cook e Mertz sono rimasti sorpresi quanto tutti gli altri. "Ho dovuto fare una lunga passeggiata prima di fare qualsiasi altra cosa", ha detto Mertz.

Valiant ha avuto un'anteprima del miglioramento di Williams rispetto al suo risultato decennale durante il suo tragitto mattutino per andare al lavoro. Per anni ha insegnato all'Università di Harvard, poco distante dall'ufficio di Williams al MIT. Si erano già conosciuti, ma non sapevano di vivere nello stesso quartiere finché non si sono incontrati per caso sull'autobus in una nevosa giornata di febbraio, poche settimane prima che il risultato fosse reso pubblico. Williams ha descritto la sua dimostrazione allo sconcertato Valiant e ha promesso di inviargli il suo articolo.

"Sono rimasto davvero molto colpito", ha detto Valiant. "Se ottieni un risultato matematico che è il migliore degli ultimi 50 anni, significa che stai facendo qualcosa di giusto."

Con la sua nuova simulazione, Williams aveva dimostrato un risultato positivo sulla potenza di calcolo dello spazio: gli algoritmi che utilizzano relativamente poco spazio possono risolvere tutti i problemi che richiedono una quantità di tempo leggermente maggiore. Poi, usando solo poche righe di matematica, ha capovolto il risultato e ha dimostrato un risultato negativo sulla potenza di calcolo del tempo: almeno alcuni problemi non possono essere risolti se non si utilizza più tempo che spazio. Questo secondo risultato, più limitato, è in linea con le aspettative dei ricercatori. La cosa strana è come Williams sia arrivato a questo punto, dimostrando prima un risultato che si applica a tutti gli algoritmi, indipendentemente dai problemi che risolvono.

"Faccio ancora fatica a crederci", ha detto Williams. "Sembra troppo bello per essere vero."

Espresso in termini qualitativi, il secondo risultato di Williams potrebbe sembrare la soluzione a lungo ricercata al problema P contro PSPACE. La differenza è una questione di scala. P e PSPACE sono classi di complessità molto ampie, mentre i risultati di Williams operano a un livello più preciso. Ha stabilito un divario quantitativo tra la potenza dello spazio e quella del tempo, e per dimostrare che PSPACE è maggiore di P, i ricercatori dovranno ampliare questo divario molto, molto.

È una sfida ardua, simile a quella di aprire una crepa sul marciapiede con un piede di porco finché non diventa larga quanto il Grand Canyon. Ma potrebbe essere possibile arrivarci utilizzando una versione modificata della procedura di simulazione di Williams che ripete il passaggio chiave più volte, risparmiando un po' di spazio ogni volta. È come un modo per aumentare ripetutamente la lunghezza del piede di porco: rendilo abbastanza grande e potrai aprire qualsiasi cosa. Questo miglioramento ripetuto non funziona con la versione attuale dell'algoritmo, ma i ricercatori non sanno se si tratti di una limitazione fondamentale.

"Potrebbe essere un collo di bottiglia definitivo, o potrebbe durare 50 anni", ha detto Valiant. "Oppure potrebbe essere qualcosa che forse qualcuno potrà risolvere la prossima settimana."

Se il problema verrà risolto la prossima settimana, Williams si prenderà a calci. Prima di scrivere l'articolo, ha passato mesi a cercare, senza successo, di estendere il suo risultato. Ma anche se tale estensione non fosse possibile, Williams è fiducioso che un'ulteriore esplorazione spaziale porterà sicuramente a qualcosa di interessante, forse a progressi su un problema completamente diverso.

"Non riesco mai a dimostrare esattamente le cose che voglio dimostrare", ha detto. "Ma spesso, ciò che dimostro è molto meglio di ciò che volevo."

Nota dell'editore: Scott Aaronson è membro del comitato consultivo di Quanta Magazine.

Articolo originale ripubblicato con autorizzazione di Quanta Magazine , una pubblicazione editorialmente indipendente della Simons Foundation, la cui missione è quella di migliorare la comprensione pubblica della scienza, occupandosi degli sviluppi e delle tendenze della ricerca in matematica, scienze fisiche e della vita.