Immagina di essere alla ricerca della natura stessa del calcolo. Sei nel profondo del deserto, lontano da qualsiasi sentiero, e imperscrutabile messaggi sono scolpiti nei tronchi degli alberi intorno a te: BPP, AC⁰[m], Σ₂P, YACC e centinaia di altri. I glifi stanno cercando di dirti qualcosa, ma da dove cominciare? Non riesci nemmeno a tenerli tutti dritti.

Pochi ricercatori hanno fatto altrettanto Russel Impagliazzo per superare questo apparente caos. Per 40 anni, Impagliazzo ha lavorato in prima linea nella teoria della complessità computazionale, lo studio della difficoltà intrinseca di diversi problemi. La domanda aperta più famosa in questo campo, chiamata problema P contro NP, chiede se molti problemi computazionali apparentemente difficili siano in realtà facili, con il giusto algoritmo. Una risposta avrebbe implicazioni di vasta portata per la scienza e la sicurezza della crittografia moderna.

Negli anni '1980 e '1990 Impagliazzo ha avuto un ruolo di primo piano nell'unificazione del fondamenti teorici della crittografia. Nel 1995, articolò il significato di questi nuovi sviluppi in un articolo iconico che riformulò le possibili soluzioni a P rispetto a NP e una manciata di problemi correlati nel linguaggio di cinque mondi ipotetici potremmo abitare, bizzarramente soprannominati Algorithmica, Heuristica, Pessiland, Minicrypt e Cryptomania. I cinque mondi di Impagliazzo hanno ispirato una generazione di ricercatori e continuano a guidare la ricerca nel fiorente sottocampo della meta-complessità.

E questi non sono gli unici mondi che ha immaginato. Impagliazzo è da sempre un appassionato di giochi di ruolo da tavolo come Dungeons and Dragons, e si diletta nell'inventare nuove serie di regole e nuove impostazioni da esplorare. Lo stesso spirito giocoso anima la sua pratica trentennale di commedia improvvisata.

Impagliazzo ha svolto anche un lavoro fondamentale chiarendo il ruolo fondamentale della casualità nel calcolo. Alla fine degli anni '1970, gli scienziati informatici scoprirono che a volte la casualità può accadere migliorare gli algoritmi per risolvere problemi intrinsecamente deterministici: una scoperta controintuitiva che ha lasciato perplessi i ricercatori per anni. Il lavoro di Impagliazzo con il teorico della complessità Avi Wigderson e altri ricercatori negli anni '1990 hanno dimostrato che se certi problemi computazionali sono davvero fondamentalmente difficili, allora è sempre possibile per convertire algoritmi che utilizzano la casualità in algoritmi deterministici. E viceversa, dimostrando che la casualità può essere eliminata da qualsiasi algoritmo dimostrerebbe anche che esistono problemi veramente difficili.

Quanta ha parlato con Impagliazzo della differenza tra problemi difficili ed enigmi difficili, consultando oracoli e le lezioni di matematica della commedia improvvisata. L'intervista è stata condensata e modificata per chiarezza.

Quando hai iniziato ad interessarti alla matematica?

Ero interessato alla matematica ancor prima di sapere veramente di cosa si trattasse. In terza elementare, i miei voti in matematica cominciarono a peggiorare perché dovevamo memorizzare le tabelline, e io mi rifiutai. Mia madre disse: "Ma Russell, tu adori la matematica, perché non lo fai?" E ho detto: “Questa non è matematica, è memorizzazione. La vera matematica non implica la memorizzazione. Tutto quello che avevo imparato a quel punto era l'aritmetica, quindi non sono sicuro da dove ho preso l'idea che la matematica riguardasse concetti astratti.

E l'informatica? Alcune parti del campo sono molto astratte, ma non sono ciò che la maggior parte delle persone incontra per la prima volta.

Al liceo avevo seguito un corso di programmazione in BASIC, ma era davvero difficile portare a termine qualcosa. I programmi dovevano essere trasferiti su nastri di carta, che dovevano essere fatti passare attraverso questo computer molto vecchio che spesso non funzionava correttamente e strappava la carta a metà. Quindi pensavo che l’informatica fosse terribilmente noiosa.

Avevo intenzione di studiare logica. Ma molti concetti, quando si tentava di formalizzarli effettivamente, implicavano calcoli e soprattutto limiti al calcolo. Domande come “Come facciamo a sapere che le cose in matematica sono vere?” e “Come comprendiamo la difficoltà di fare matematica?” ha portato all’informatica teorica e in particolare alla teoria della complessità.

Alcuni dei tuoi lavori più famosi esplorano le connessioni tra crittografia e teoria della complessità computazionale. Perché questi due campi sono correlati?

Quando imposti un sistema crittografico, devi distinguere tra gli utenti legittimi, ovvero le persone a cui vuoi concedere l'accesso, e tutti gli altri. Problemi computazionalmente difficili ci danno un modo per distinguere questi gruppi in base a ciò che sanno. Ma se vuoi che conoscere la risposta a un problema sia un modo per distinguere due gruppi di persone, non puoi semplicemente usare un problema difficile: hai bisogno di un puzzle difficile.

Qual è la differenza tra un problema e un puzzle?

In generale, la persona che pone un problema potrebbe non conoscere la risposta. Un puzzle è un problema progettato con una risposta in mente. Allora perché abbiamo bisogno di un puzzle? Perché dobbiamo essere in grado di determinare se la persona che presumibilmente ha risolto il problema lo ha effettivamente fatto. Nella vita di tutti i giorni utilizziamo i puzzle per divertimento, ma li usiamo anche in classe per verificare se le persone hanno capito il materiale. Questo è ciò che accade nella crittografia: utilizziamo enigmi per testare la conoscenza di qualcuno.

La differenza tra i cinque mondi è il modo in cui rispondono alle domande “Ci sono problemi difficili?” e "Ci sono enigmi difficili?"

Come si svolgono queste diverse risposte?

Nel primo mondo, Algorithmica, nessun problema è difficile. Non devi sapere come qualcuno ha progettato il tuo problema: puoi sempre risolverlo. L’euristica sta dicendo: “Beh, forse alcuni problemi sono difficili”. Poi arriviamo a Pessiland, dove molti problemi sono difficili, ma la maggior parte degli enigmi non lo sono. Quasi tutti i problemi che invento di cui conosco la soluzione, anche tu sarai in grado di risolverli. Tutti questi mondi sono dannosi per la crittografia.

In Minicrypt, posso creare enigmi che so come risolvere e che sono comunque davvero impegnativi per te. E infine, Cryptomania è un mondo in cui due persone possono stare in un luogo pubblico dove un origliatore può sentire e insieme creare un puzzle che risulta comunque difficile per l'intercettatore.

Cosa ti ha motivato a scrivere l’articolo sui cinque mondi?

All’epoca, si sapeva che risposte diverse alla domanda P rispetto a NP avrebbero avuto un grande impatto sul tipo di problemi che possiamo risolvere e anche sul tipo di sicurezza che possiamo sperare, ma le distinzioni qualitative tra diverse forme di facilità e di sicurezza la durezza non era molto chiara.

C’era stato un articolo molto perspicace solo pochi anni prima che esponeva le distinzioni utilizzando molte domande correlate con circa 20 possibili risposte. Uno dei motivi per cui ho voluto scrivere l’articolo sui cinque mondi è che in quei pochi anni avevamo fatto enormi progressi. Sarebbe stato difficile trovare nomi per 20 mondi possibili.

Allora perché inquadrarlo in questo modo, come mondi diversi con nomi bizzarri?

Avevo accettato di scrivere questo articolo per una conferenza. Stavo sveglio fino a tarda notte cercando di capire cosa avrei detto, e da qualche parte intorno all'una di notte l'inquadratura dei diversi mondi sembrava una buona idea. E poi l'ho letto la mattina dopo e mi sembrava ancora un'idea valida: era un modo per mostrare come queste idee avrebbero effettivamente influenzato il mondo senza rimanere intrappolati nei dettagli quantitativi. Ciò che mi rende più felice di questo articolo è che ho sentito da persone che svolgono ricerche sulla complessità che questo è stato l'articolo che li ha interessati al campo come studenti universitari.

I ricercatori hanno escluso qualcuno dei cinque mondi possibili?

In realtà ne stiamo aggiungendo di più: le persone hanno iniziato a parlare Obfustopia come un mondo di strumenti crittografici ancora più potenti. È un po' deprimente che abbiamo fatto così tanti progressi alla fine degli anni '1980 e da allora non abbiamo eliminato nessun mondo. Ma d'altra parte, sappiamo molto di più sulle connessioni tra i mondi e abbiamo un quadro molto più chiaro di come sarebbe ogni mondo.

I mondi ipotetici svolgono anche un altro ruolo nella teoria della complessità, nelle dimostrazioni che presuppongono l’esistenza degli “oracoli”. Quindi, prima di tutto, cos’è esattamente un oracolo?

Immagina che qualcuno costruisca un dispositivo ingegnoso in grado di risolvere qualche problema senza che noi conosciamo un algoritmo per risolverlo. Ecco cos'è un oracolo. Se avessimo un dispositivo così miracoloso e lo mettessimo nei nostri computer, potrebbe spostare il confine tra ciò che è calcolabile e ciò che non lo è.

I ricercatori pensano che queste scatole magiche possano effettivamente esistere?

No, probabilmente non esistono. All'inizio, i risultati degli oracoli erano alquanto controversi perché erano ipotetici. Ma un modo in cui possono essere molto illuminanti è quando l’oracolo viene utilizzato per modellare una situazione ideale. Supponiamo che tu stia cercando di dimostrare che A non implica necessariamente B. Inizi con l'impostazione in cui hai l'A più estremo e dimostri che questo non è ancora sufficiente per garantire B. Se riesci a dimostrare che, anche se tutte le probabilità sono a tuo favore non puoi ancora provare qualcosa, questa è una prova davvero forte che sarà difficile da dimostrare.

Hai anche scoperto collegamenti tra durezza computazionale e casualità. Come funziona questa connessione?

È davvero un modo per dire che se non capisci qualcosa, potrebbe sembrare casuale. Supponiamo che io dica che sto pensando a un numero compreso tra uno e mille. Se scelgo il numero a caso, hai una possibilità su mille di indovinarlo. E se chiedo, seguendo i Monty Python, "In miglia all'ora, qual è la velocità media di una rondine europea?" hai più o meno le stesse possibilità. Probabilmente va a più di un miglio all'ora e probabilmente non va a più di mille miglia all'ora.

In realtà questo non è casuale: è una domanda a cui è possibile rispondere in modo deterministico. Potremmo semplicemente misurare tutte le rondini che volano in giro, ma è difficile determinarlo con risorse limitate, come non avere un budget per misurare la velocità delle rondini e non avere una scorta infinita di rondini.

Quindi l'intuizione è che problemi difficili di cui non conosciamo le soluzioni possono fornire una fonte di numeri “pseudocasuali” che sembrano casuali.

A proposito di Monty Python, so che fai commedie improvvisate da molto tempo ormai: come hai iniziato?

Ho iniziato come assistente professore a San Diego nel 1991. E intorno al '94 o giù di lì, ho pensato: "Non ho molta vita al di fuori del dipartimento". Così ho preso il giornale settimanale gratuito e ho guardato l'elenco dei club e delle attività. Ho eliminato tutto tranne la commedia improvvisata: pensavo che fosse almeno plausibile che mi andasse bene. Ho conosciuto mia moglie in quel corso per principianti.

Cosa pensava?

Dice che sono stato davvero orribile. Quando sei un logico, sei addestrato a pensare sempre alle sfumature di ogni parola. Non vuoi dire qualcosa di sbagliato. L'improvvisazione è fantastica in quanto capovolge la situazione: il punto non è dire qualcosa di perfetto ma inventare qualcosa velocemente. È stato l'opposto del resto della mia vita.

La mia attuale moglie si è presa una pausa dalle lezioni e quando è tornata un anno dopo sono riuscito a impressionarla. Questo è successo 30 anni fa. Seguo ancora lo stesso corso con lo stesso istruttore.

Fare improvvisazione ha cambiato il tuo modo di affrontare la tua ricerca?

È una buona pratica non essere ipercritici riguardo a ogni pensiero che hai. Ciò è particolarmente utile nelle collaborazioni. Quando lavoravo con altre persone, dicevo cose del tipo: “Ma quell'idea non funzionerà per il seguente motivo. Questo non è letteralmente vero. Nell'improvvisazione, dovresti sempre accettare ciò che dice il tuo partner. E penso che sia un buon atteggiamento da avere, soprattutto quando fai ricerche con gli studenti: non respingere qualcosa che dicono solo perché sai che non è corretto. Ci sono molte buone idee che non sono corrette al 100%.

Tipo cosa?

Quando stai cercando di ottenere un'intuizione per un problema, una cosa che aiuta è iniziare con alcuni presupposti semplificatori. Queste ipotesi di solito non sono vere, ma possono aiutarti a elaborare una tabella di marcia. Di': “Se avessi un elefante, potrei superare le montagne. Ovviamente non ho un elefante. Ma se lo facessi, ecco come lo farei. E poi realizzi: “Beh, forse non ho bisogno di un elefante per questo passo. Un mulo andrebbe bene."

Che mi dici del tuo amore per i giochi di ruolo? Questo ha influenzato il tuo lavoro?

Potrebbe non aver influenzato tutta la mia ricerca, ma sicuramente ha influenzato il mio articolo sui cinque mondi. Ho sempre avuto un interesse generale per il fantasy e la fantascienza e per l'ideazione di diversi mondi possibili: come sarebbero le cose se tutto fosse diverso?

Perché i giochi di ruolo sono un modo così avvincente per esplorare mondi ipotetici?

Le persone appassionate di narrativa speculativa hanno sempre inventato mondi. Tolkien è famoso soprattutto per questo, e aveva un'immaginazione così massiccia che il suo mondo sembrava davvero vissuto. Per quelli di noi che non sono così fantasiosi, il modo migliore per raggiungere questo obiettivo è invitare le persone nella propria ambientazione e un gioco è un modo per farlo. Ora non è solo il mio mondo. Potrebbe essere iniziato come l'avevo immaginato, ma proprio come in ogni collaborazione, grazie al contributo di tutti gli altri, si è evoluto ben oltre.