Per più di 40 anni Avi Wigderson ha studiato i problemi. Ma in quanto teorico della complessità computazionale, non è necessariamente interessato alle risposte a questi problemi. Spesso vuole solo sapere se sono risolvibili o meno e come dirlo. "La situazione è ridicola", ha detto Wigderson, scienziato informatico presso l'Institute for Advanced Study di Princeton, nel New Jersey. Non importa quanto sembri difficile una domanda, un modo efficace per rispondere potrebbe nascondersi fuori portata. “Per quanto ne sappiamo, per ogni problema che affrontiamo e cerchiamo di risolvere, non possiamo escludere che esista un algoritmo in grado di risolverlo. Questo è il problema più interessante per me”.

Oggi Wigderson è stato nominato vincitore del Premio AM Turing, ampiamente considerato uno dei massimi riconoscimenti in informatica, per i suoi contributi fondamentali alla teoria del calcolo. Il lavoro di Wigderson ha toccato quasi ogni area del campo. I suoi colleghi, collaboratori e allievi affermano che trova costantemente ponti inaspettati tra aree disparate. E il suo lavoro sulla casualità e il calcolo, iniziato negli anni '1990, ha rivelato profonde connessioni tra matematica e informatica che sono alla base delle indagini odierne.

Madhu Sudan, uno scienziato informatico dell'Università di Harvard che ha vinto nel 2002 il Premio Rolf Nevanlinna (ora chiamato Premio Abacus), ha affermato che l'influenza di Wigderson sul campo è impossibile da non notare. "È molto difficile lavorare in qualsiasi campo dell'informatica senza intersecarsi effettivamente con il lavoro di Avi", ha detto Sudan. "E ovunque trovi intuizioni molto profonde." Alla fine degli anni ’1980, ad esempio, il Sudan lavorò con Wigderson su un articolo che indagava le connessioni tra alcune funzioni matematiche e i polinomi. Quel lavoro ha lanciato l'intera carriera del Sudan. "Questo è tipico di Avi", ha detto Sudan. "Entra in uno spazio, fa le domande giuste e poi va avanti."

Wigderson è cresciuto ad Haifa, in Israele, come uno dei tre figli di un'infermiera e di un ingegnere elettrico, entrambi sopravvissuti all'Olocausto. Suo padre amava i puzzle ed era intensamente interessato alle idee fondamentali della matematica, che condivideva con i suoi figli. "È la persona da cui sono stato infettato da questo virus", ha detto Wigderson. Quando iniziò l'università negli anni '1970, al Technion di Haifa, voleva specializzarsi in matematica, ma i suoi genitori lo indirizzarono invece verso l'informatica. "Hanno pensato che forse era una buona idea che avrei avuto un lavoro quando avrò finito", ha detto.

Trovò un campo ricco di domande profonde e senza risposta che avevano un cuore matematico. Uno dei suoi primi sforzi pionieristici si concentrò su un'apparente contraddizione: se fosse possibile convincere qualcun altro che un'affermazione matematica era stata dimostrata senza mostrare come.

"La persona che vede la prova non impara nulla sulla prova stessa", ha detto Ran Raz, uno scienziato informatico dell'Università di Princeton. Nel 1985 Shafi Goldwasser, Silvio Micali e Charles Rackoff introdussero questo concetto di dimostrazioni interattive a conoscenza zero, dimostrandone l'utilizzo per alcune affermazioni. Wigderson, insieme a Micali e Oded Goldreich, in seguito espose quell'idea, esponendo le condizioni che dimostrano che se un'affermazione può essere dimostrata, ha anche una prova a conoscenza zero.

“Questo è un risultato chiave nella crittografia; è estremamente centrale”, ha detto Raz. Utilizzando una prova a conoscenza zero, qualcuno può dimostrare di aver crittografato o firmato correttamente un messaggio utilizzando la propria chiave segreta, senza rivelare alcuna informazione al riguardo. "Avi ha ottenuto alcuni risultati estremamente importanti nel campo della crittografia, e questo potrebbe essere il più importante."

Ma forse il risultato più fondamentale di Wigderson risiede in un’altra area: collegare la durezza computazionale all’analisi casualità. Verso la fine degli anni ’1970, gli informatici si erano resi conto che, per molti problemi difficili, gli algoritmi che utilizzavano la casualità, chiamati anche algoritmi probabilistici, potevano ampiamente superare le loro alternative deterministiche. In un 1977 prova, ad esempio, Robert Solovay e Volker Strassen introdussero un algoritmo randomizzato in grado di determinare se un numero è primo più velocemente dei migliori algoritmi deterministici dell'epoca.

Per alcuni problemi, gli algoritmi probabilistici possono puntare a quelli deterministici. All'inizio degli anni '1980, Wigderson lavorò con Richard Karp dell'Università della California, Berkeley, per collegare l'idea di casualità a problemi considerati computazionalmente difficili, il che significa che nessun algoritmo deterministico noto può risolverli in un periodo di tempo ragionevole. "Non sappiamo come dimostrare che sono duri", ha detto Wigderson. Tuttavia, lui e Karp hanno trovato un algoritmo randomizzato per un determinato problema difficile che sono stati successivamente in grado di derandomizzare, scoprendo di fatto un algoritmo deterministico per esso. Nello stesso periodo, altri ricercatori hanno dimostrato come i presupposti di durezza computazionale nei problemi di crittografia potrebbero consentire la derandomizzazione in generale.

L'irragionevole efficacia della casualità lo ha portato a pensare alla natura della casualità stessa. Lui, come altri ricercatori dell'epoca, si chiese quanto fosse necessario per una soluzione efficace dei problemi e in quali condizioni potesse essere eliminato del tutto. “Inizialmente non era chiaro se questa fosse solo la nostra stupidità, che non possiamo eliminare la casualità”, ha detto. “Ma la domanda più importante era se la casualità potesse sempre essere eliminata in modo efficiente oppure no”. Si rese conto che la necessità di casualità era intimamente legata alla difficoltà computazionale del problema.

Per un carta 1994, lui e lo scienziato informatico Noam Nisan hanno illuminato quella connessione. Hanno dimostrato che se esistono problemi naturali difficili, come sospetta la maggior parte degli scienziati informatici, allora ogni algoritmo randomizzato efficiente può essere sostituito da uno deterministico efficiente. "Puoi sempre eliminare la casualità", ha detto Wigderson.

È importante sottolineare che hanno scoperto che gli algoritmi deterministici possono utilizzare sequenze “pseudocasuali” – stringhe di dati che sembrano casuali ma non lo sono. Hanno anche mostrato come qualsiasi problema difficile possa essere utilizzato per costruire un generatore pseudocasuale. Inserendo i bit pseudocasuali (invece di quelli casuali) in un algoritmo probabilistico si otterrà un algoritmo deterministico efficiente per lo stesso problema.

Sudan ha affermato che la carta ha aiutato gli scienziati informatici a riconoscere i gradi di casualità che potrebbero aiutare a rivelare la complessità dei problemi difficili e come risolverli. "Non è solo casualità ma percezione della casualità", ha detto. "Questa è la chiave."

Il Sudan sottolinea che la casualità sembra apparire ovunque ma, in verità, è estremamente difficile da trovare. "La gente ti dice che le cifre del pi greco sembrano casuali, o che la sequenza di numeri primi sembra casuale", ha detto. "Sono completamente determinati, ma ci sembrano casuali." La percezione della casualità, ha detto, è oggi al centro dell’informatica. "E questo è qualcosa che Avi ha promosso ampiamente."

La casualità è diventata una risorsa potente nella teoria della complessità, ma è sfuggente. Il lancio della moneta e quello dei dadi, sottolinea Wigderson, non sono realmente casuali: se si hanno abbastanza informazioni sul sistema fisico, il risultato è del tutto prevedibile. La perfetta casualità, ha detto, è sfuggente e difficile da verificare.

Ma per Wigerson, gli esempi di elaborazione sono ovunque: non solo negli smartphone, nei laptop e negli algoritmi di crittografia, ma anche nei sistemi biologici e fisici. Negli ultimi decenni, le scoperte della teoria del calcolo hanno fornito spunti su una serie di problemi inaspettati, dallo sciame di uccelli e dai risultati elettorali alle reazioni biochimiche nel corpo. “Fondamentalmente, qualsiasi processo naturale è un’evoluzione che puoi vedere come calcolo, quindi puoi studiarla come tale. Quasi tutto conta”.