Avi Wigderson, pionier al teoriei complexității, câștigă premiul Turing | Revista Quanta

De mai bine de 40 de ani, Avi Wigderson a studiat problemele. Dar, ca teoretician al complexității computaționale, nu îi pasă neapărat de răspunsurile la aceste probleme. Adesea vrea doar să știe dacă sunt rezolvabile sau nu și cum să spună. „Situația este ridicolă”, a spus Wigderson, un informatician la Institutul pentru Studii Avansate din Princeton, New Jersey. Indiferent cât de grea ar părea o întrebare, o modalitate eficientă de a răspunde la ea ar putea fi ascunsă la îndemână. „Din câte știm, pentru fiecare problemă cu care ne confruntăm și încercăm să o rezolvăm, nu putem exclude că are un algoritm care o poate rezolva. Aceasta este cea mai interesantă problemă pentru mine.”

Astăzi, Wigderson a fost desemnat câștigătorul concursului Premiul AM Turing, considerată pe scară largă una dintre distincțiile de top în informatică, pentru contribuțiile sale fundamentale la teoria calculului. Munca lui Wigderson a atins aproape fiecare zonă a terenului. Colegii, colaboratorii și mentorii săi spun că găsește în mod constant punți neașteptate între zone disparate. Iar munca sa despre aleatoriu și calcul, începând cu anii 1990, a dezvăluit conexiuni profunde între matematică și informatică care stau la baza investigațiilor de astăzi.

Madhu Sudan, un informatician de la Universitatea Harvard care a câștigat în 2002 Premiul Rolf Nevanlinna (numit în prezent Premiul Abacus), a spus că influența lui Wigderson în domeniu este imposibil de ratat. „Este foarte greu să lucrezi în orice spațiu al informaticii fără a te intersecta efectiv cu munca lui Avi”, a spus Sudan. „Și peste tot, găsești perspective foarte profunde.” La sfârșitul anilor 1980, de exemplu, Sudan a lucrat cu Wigderson la o lucrare care investighează conexiunile dintre anumite funcții matematice și polinoame. Acea activitate a lansat întreaga carieră a Sudanului. „Acest lucru este tipic pentru Avi”, a spus Sudan. „Intră într-un spațiu, pune întrebările potrivite și apoi merge mai departe.”

Wigderson a crescut în Haifa, Israel, ca unul dintre cei trei fii ai unei asistente medicale și ai unui inginer electrician, ambii supraviețuitori ai Holocaustului. Tatăl său iubea puzzle-urile și era intens interesat de ideile fundamentale din matematică, pe care le împărtășea copiilor săi. „El este tipul de la care am fost infectat cu acest virus”, a spus Wigderson. Când și-a început facultatea în anii 1970, la Technion din Haifa, a vrut să se specializeze în matematică, dar părinții lui l-au îndrumat în schimb către informatică. „Ei s-au gândit că poate că ar fi o idee bună că voi avea o slujbă când termin”, a spus el.

A găsit un domeniu bogat cu întrebări profunde, fără răspuns, care erau matematice în esen. Unul dintre primele sale eforturi inovatoare s-a concentrat pe o aparentă contradicție: dacă a fost posibil să convingi pe altcineva că o afirmație matematică a fost dovedită fără a arăta cum.

„Persoana care vede dovada nu învață nimic despre dovada în sine”, a spus Ran Raz, un informatician la Universitatea Princeton. În 1985, Shafi Goldwasser, Silvio Micali și Charles Rackoff au introdus acest concept de dovezi interactive fără cunoștințe, demonstrând utilizarea sa pentru câteva afirmații. Wigderson, împreună cu Micali și Oded Goldreich, au expus ulterior această idee, stabilind condițiile care arată că, dacă o afirmație poate fi dovedită, aceasta are, de asemenea, o dovadă a cunoștințelor zero.

„Acesta este un rezultat cheie în criptografie; este extrem de central”, a spus Raz. Folosind o dovadă de zero cunoștințe, cineva poate dovedi că a criptat sau a semnat corect un mesaj folosind cheia secretă, fără a dezvălui nicio informație despre acesta. „Avi are câteva rezultate extrem de importante în criptografie, iar acesta poate fi cel mai important dintre ele.”

Dar, probabil, rezultatul cel mai fundamental al lui Wigderson se află într-un alt domeniu: legarea durității de calcul cu dezordine. Până la sfârșitul anilor 1970, informaticienii și-au dat seama că, pentru multe probleme dificile, algoritmii care foloseau aleator, numiți și algoritmi probabilistici, puteau depăși cu mult alternativele lor deterministe. Într-o 1977 dovada, de exemplu, Robert Solovay și Volker Strassen au introdus un algoritm randomizat care ar putea determina dacă un număr este prim mai rapid decât cei mai buni algoritmi determiniști ai vremii.

Pentru unele probleme, algoritmii probabilistici pot indica unele deterministe. La începutul anilor 1980, Wigderson a lucrat cu Richard Karp de la Universitatea din California, Berkeley, pentru a conecta ideea aleatoriei cu probleme considerate grele din punct de vedere computațional, ceea ce înseamnă că niciun algoritm deterministic cunoscut nu le poate rezolva într-o perioadă rezonabilă de timp. „Nu știm cum să dovedim că sunt duri”, a spus Wigderson. Cu toate acestea, el și Karp au găsit un algoritm randomizat pentru o anumită problemă dificilă pe care ulterior au putut să o derandomizeze, dezvăluind efectiv un algoritm determinist pentru aceasta. Aproximativ în același timp, alți cercetători au arătat cum ipotezele de duritate computațională în problemele de criptografie ar putea permite derandomizarea în general.

Eficacitatea nerezonabilă a aleatoriei l-a determinat să se gândească la natura aleatoriei în sine. El, ca și alți cercetători de la acea vreme, a pus la îndoială cât de necesar este pentru rezolvarea eficientă a problemelor și în ce condiții ar putea fi eliminat complet. „Inițial, nu era clar dacă aceasta era doar propria noastră prostie, că nu putem elimina aleatoriile”, a spus el. „Dar întrebarea mai mare a fost dacă aleatoriile poate fi întotdeauna eliminată eficient sau nu.” Și-a dat seama că nevoia de aleatorie era strâns legată de dificultatea de calcul a problemei.

Pentru o Hârtie 1994, el și informaticianul Noam Nisan au luminat această conexiune. Ei au demonstrat că, dacă există probleme naturale grele, așa cum bănuiesc majoritatea informaticienilor, atunci fiecare algoritm randomizat eficient poate fi înlocuit cu unul determinist eficient. „Puteți elimina întotdeauna aleatorietatea”, a spus Wigderson.

Foarte important, ei au descoperit că algoritmii determiniști pot folosi secvențe „pseudoratoare” - șiruri de date care par aleatorii, dar nu sunt. De asemenea, au arătat cum orice problemă dificilă poate fi folosită pentru a construi un generator pseudoaleator. Alimentarea biților pseudoaleatori (în loc de cei aleatori) într-un algoritm probabilist va avea ca rezultat unul determinist eficient pentru aceeași problemă.

Sudanul a spus că lucrarea a ajutat oamenii de știință în informatică să recunoască grade de aleatorie care ar putea ajuta la dezvăluirea complexității problemelor dificile și a modului de rezolvare a acestora. „Nu este vorba doar de aleatoriu, ci de percepții ale aleatoriei”, a spus el. „Aceasta este cheia.”

Sudan subliniază că aleatoriu pare să apară peste tot, dar este, de fapt, extrem de greu de găsit. „Oamenii vă spun că cifrele lui pi par aleatorii, sau secvența de numere care sunt prime arată aleatoare”, a spus el. „Sunt complet hotărâți, dar ni se par aleatorii.” Percepția aleatoriei, a spus el, se află în centrul informaticii de astăzi. „Și acesta este ceva pe care Avi l-a promovat foarte mult.”

Aleatoria a devenit o resursă puternică în teoria complexității, dar este evazivă. Răsturnările de monede și zarurile, subliniază Wigderson, nu sunt cu adevărat aleatorii: dacă aveți suficiente informații despre sistemul fizic, atunci rezultatul este complet previzibil. Aleatoritatea perfectă, a spus el, este evazivă și greu de verificat.

Dar pentru Wigerson, exemplele de calcul sunt peste tot – nu doar în smartphone-uri și laptopuri și în algoritmii de criptare, ci și în sistemele biologice și fizice. În ultimele decenii, descoperirile din teoria calculului au oferit perspective asupra unei game de probleme neașteptate, de la păsări care roiesc și rezultatele alegerilor până la reacții biochimice din organism. „Practic, orice proces natural este o evoluție pe care o poți privi ca calcul, așa că o poți studia ca atare. Aproape totul calculează.”