Več kot 40 let Avi Wigderson preučuje probleme. Toda kot teoretik računalniške zapletenosti mu ni nujno, da ga zanimajo odgovori na te težave. Pogosto samo želi vedeti, ali so rešljive ali ne, in kako povedati. "Situacija je smešna," je rekel Wigderson, računalniški znanstvenik na Inštitutu za napredne študije v Princetonu v New Jerseyju. Ne glede na to, kako težko se zdi vprašanje, se lahko učinkovit način odgovora nanj skriva izven dosega. »Kolikor vemo, za vsako težavo, s katero se soočimo in jo poskušamo rešiti, ne moremo izključiti, da ima algoritem, ki jo lahko reši. To je zame najbolj zanimiv problem.”

Danes je bil Wigderson imenovan za zmagovalca Nagrada AM Turing, ki velja za enega največjih priznanj v računalništvu, zaradi njegovih temeljnih prispevkov k teoriji računanja. Wigdersonovo delo se je dotaknilo skoraj vseh področij. Njegovi kolegi, sodelavci in mentoriranci pravijo, da vedno znova najde nepričakovane mostove med različnimi področji. In njegovo delo o naključnosti in računanju, ki se je začelo v devetdesetih letih prejšnjega stoletja, je razkrilo globoke povezave med matematiko in računalništvom, ki so podlaga za današnje preiskave.

Madhu Sudan, računalniški znanstvenik na univerzi Harvard, ki je leta 2002 prejel nagrado Rolfa Nevanlinna (danes imenovana nagrada Abacus), je dejal, da je Wigdersonov vpliv na tem področju nemogoče spregledati. "Zelo težko je delati na katerem koli področju računalništva, ne da bi se dejansko presekali z Avijevim delom," je dejal Sudan. "In povsod najdeš zelo globoka spoznanja." V poznih osemdesetih letih prejšnjega stoletja je na primer Sudan delal z Wigdersonom na dokumentu, ki je raziskoval povezave med nekaterimi matematičnimi funkcijami in polinomi. To delo je sprožilo celotno Sudanovo kariero. "To je značilno za Avija," je dejal Sudan. "Vstopi v prostor, postavi prava vprašanja in nato gre naprej."

Wigderson je odraščal v Haifi v Izraelu kot eden od treh sinov medicinske sestre in inženirja elektrotehnike, ki sta oba preživela holokavst. Njegov oče je oboževal uganke in se močno zanimal za temeljne ideje v matematiki, ki jih je delil s svojimi otroki. "On je tip, od katerega sem se okužil s tem virusom," je dejal Wigderson. Ko je v sedemdesetih letih prejšnjega stoletja začel študirati na Technionu v Haifi, je želel študirati matematiko, a so ga starši namesto tega usmerili v računalništvo. "Mislili so, da je morda dobra ideja, da bi imel službo, ko končam," je dejal.

Našel je področje, bogato z globokimi, neodgovorjenimi vprašanji, ki so bila v srcu matematična. Eno njegovih prvih prelomnih prizadevanj se je osredotočilo na navidezno protislovje: ali je mogoče nekoga prepričati, da je bila matematična izjava dokazana, ne da bi pokazal, kako.

"Oseba, ki vidi dokaz, se ne nauči ničesar o samem dokazu," je rekel Ran Raz, računalniški znanstvenik na univerzi Princeton. Leta 1985 so Shafi Goldwasser, Silvio Micali in Charles Rackoff predstavili ta koncept interaktivni dokazi brez znanja, ki prikazuje njegovo uporabo za nekaj izjav. Wigderson je skupaj z Micali in Odedom Goldreichom pozneje razložil to zamisel in navedel pogoje, ki kažejo, da če je izjavo mogoče dokazati, ima tudi dokaz nič znanja.

»To je ključni rezultat v kriptografiji; je zelo osrednjega pomena,« je dejal Raz. Z uporabo dokazila brez znanja lahko nekdo dokaže, da je pravilno šifriral ali podpisal sporočilo s svojim skrivnim ključem, ne da bi razkril kakršne koli informacije o njem. "Avi ima nekaj izjemno pomembnih rezultatov v kriptografiji in ta je morda najpomembnejši med njimi."

Toda morda Wigdersonov najbolj temeljni rezultat leži na drugem področju: povezovanje računalniške trdote z naključnost. Do poznih sedemdesetih let prejšnjega stoletja so računalniški znanstveniki ugotovili, da lahko algoritmi, ki uporabljajo naključnost, imenovani tudi verjetnostni algoritmi, za številne težke probleme močno prehitijo njihove deterministične alternative. V 1977 dokaz, na primer, sta Robert Solovay in Volker Strassen predstavila naključni algoritem, ki bi lahko ugotovil, ali je število praštevilo hitreje kot najboljši deterministični algoritmi tistega časa.

Za nekatere težave lahko verjetnostni algoritmi kažejo na deterministične. V zgodnjih osemdesetih letih prejšnjega stoletja je Wigderson sodeloval z Richardom Karpom s kalifornijske univerze Berkeley, da bi povezal idejo naključnosti s problemi, ki veljajo za računsko težke, kar pomeni, da jih noben znani deterministični algoritm ne more rešiti v razumnem času. "Ne vemo, kako dokazati, da so trdi," je dejal Wigderson. Vendar sta on in Karp našla randomiziran algoritem za določeno težko težavo, ki sta ga pozneje lahko derandomizirala in zanjo dejansko odkrila deterministični algoritem. Približno v istem času so drugi raziskovalci pokazali, kako bi lahko predpostavke o računalniški trdoti pri težavah s kriptografijo omogočile derandomizacijo na splošno.

Nerazumna učinkovitost naključnosti ga je vodila k razmišljanju o naravi naključnosti same. Tako kot drugi tedanji raziskovalci se je spraševal, kako nujen je za učinkovito reševanje problemov in pod kakšnimi pogoji ga je mogoče popolnoma odpraviti. "Na začetku ni bilo jasno, ali je to samo naša lastna neumnost, da ne moremo odstraniti naključnosti," je dejal. "Toda večje vprašanje je bilo, ali je naključnost vedno mogoče učinkovito odpraviti ali ne." Spoznal je, da je potreba po naključnosti tesno povezana z računsko težavnostjo problema.

Za Papir 1994, sta on in računalniški znanstvenik Noam Nisan osvetlila to povezavo. Dokazali so, da če obstajajo kakršni koli naravni težki problemi, kot sumi večina računalniških znanstvenikov, potem lahko vsak učinkovit naključni algoritem nadomestimo z učinkovitim determinističnim. "Vedno lahko odpravite naključnost," je dejal Wigderson.

Pomembno je, da so ugotovili, da lahko deterministični algoritmi uporabljajo "psevdonaključna" zaporedja - nize podatkov, ki se zdijo naključni, vendar niso. Pokazali so tudi, kako je mogoče kakršne koli težke probleme uporabiti za izdelavo psevdonaključnega generatorja. Vnos psevdonaključnih bitov (namesto naključnih) v verjetnostni algoritem bo povzročil učinkovitega determinističnega za isti problem.

Sudan je dejal, da je papir pomagal računalniškim znanstvenikom prepoznati stopnje naključnosti, ki bi lahko pomagale razkriti zapletenost težkih problemov in kako jih rešiti. "Ne gre samo za naključnost, ampak zaznavanje naključnosti," je dejal. "To je ključ."

Sudan poudarja, da se zdi, da se naključnost pojavlja povsod, vendar jo je v resnici izjemno težko najti. "Ljudje vam pravijo, da so številke pi videti naključne ali da je zaporedje praštevil videti naključno," je dejal. "Povsem odločni so, vendar se nam zdijo naključni." Zaznavanje naključnosti je danes v središču računalništva, je dejal. "In to je nekaj, kar je Avi močno promoviral."

Naključnost je postala močan vir v teoriji kompleksnosti, vendar je izmuzljiva. Meti kovancev in kock, poudarja Wigderson, niso resnično naključni: če imate dovolj informacij o fizičnem sistemu, je rezultat popolnoma predvidljiv. Popolna naključnost, je dejal, je izmuzljiva in jo je težko preveriti.

Toda za Wigersona so primeri računalništva povsod - ne samo v pametnih telefonih in prenosnikih ter šifrirnih algoritmih, ampak tudi v bioloških in fizičnih sistemih. V zadnjih desetletjih so ugotovitve iz teorije računanja prinesle vpogled v vrsto nepričakovanih težav, od rojenja ptic in izidov volitev do biokemičnih reakcij v telesu. »V bistvu je vsak naravni proces evolucija, na katero lahko gledate kot na računanje, tako da ga lahko kot takega preučujete. Skoraj vse se izračuna."