Rohkem kui 40 aastat on Avi Wigderson probleeme uurinud. Kuid arvutusliku keerukuse teoreetikuna ei huvita teda nende probleemide vastused. Ta tahab sageli lihtsalt teada, kas need on lahendatavad või mitte, ja kuidas seda öelda. "Olukord on naeruväärne," ütles Wigderson, arvutiteadlane Princetonis, New Jerseys asuvas Advanced Study Instituudis. Ükskõik kui raske küsimus ka ei tunduks, tõhus viis sellele vastata võib peita lihtsalt kättesaamatus kohas. "Meile teadaolevalt ei saa me iga probleemi puhul, millega silmitsi seisame ja lahendada püüame, välistada, et sellel on algoritm, mis suudab selle lahendada. See on minu jaoks kõige huvitavam probleem.

Täna kuulutati Wigderson võitjaks AM Turingi auhind, mida peetakse arvutiteaduse üheks suurimaks autasuks tema põhjapanemise eest arvutusteoorias. Wigdersoni töö on puudutanud peaaegu kõiki valdkondi. Tema kolleegid, kaastöötajad ja mentiivad ütlevad, et ta leiab pidevalt ootamatuid sildu erinevate valdkondade vahel. Ja tema 1990. aastatest alustatud tööd juhuslikkuse ja arvutuste alal näitasid sügavaid seoseid matemaatika ja arvutiteaduse vahel, mis on tänapäeva uurimiste aluseks.

Madhu Sudaan, Harvardi ülikooli arvutiteadlane, kes võitis 2002. aasta Rolf Nevanlinna auhinna (nüüdse nimega Abacus Prize), ütles, et Wigdersoni mõjust valdkonnale on võimatu mööda vaadata. "Väga raske on töötada arvutiteaduse mis tahes valdkonnas ilma Avi tööga tegelikult ristumata," ütles Sudan. "Ja kõikjal leiate väga sügavaid teadmisi." Näiteks 1980. aastate lõpus töötas Sudaan koos Wigdersoniga paberil, mis uuris seoseid teatud matemaatiliste funktsioonide ja polünoomide vahel. See töö käivitas kogu Sudaani karjääri. "See on Avi jaoks tüüpiline," ütles Sudan. "Ta satub mõnda ruumi, küsib õigeid küsimusi ja liigub siis edasi."

Wigderson grew up in Haifa, Israel, as one of three sons of a nurse and an electrical engineer, both survivors of the Holocaust. His father loved puzzles and was intensely interested in fundamental ideas in math, which he shared with his children. “He’s the guy from whom I was infected by this virus,” Wigderson said. When he started college in the 1970s, at the University of Haifa, he wanted to major in math, but his parents steered him instead to computer science. “They thought maybe it was a good idea that I would have a job when I’m done,” he said.

Ta leidis valdkonna, mis oli rikas sügavate, vastamata küsimustega, mis olid hingelt matemaatilised. Üks tema varasemaid murrangulisi jõupingutusi keskendus näilisele vastuolule: kas on võimalik kedagi teist veenda, et matemaatiline väide on tõestatud, ilma, et oleks näidatud, kuidas.

"Inimene, kes tõestust näeb, ei õpi tõestuse enda kohta midagi," ütles Ran Raz, Princetoni ülikooli arvutiteadlane. 1985. aastal tutvustasid Shafi Goldwasser, Silvio Micali ja Charles Rackoff seda kontseptsiooni nullteadmiste interaktiivsed tõendid, mis näitab selle kasutamist mõne väite puhul. Wigderson koos Micali ja Oded Goldreichiga selgitasid seda ideed hiljem, esitades tingimused, mis näitavad, et kui väidet on võimalik tõestada, omab ka nullteadmiste tõestust.

„See on krüptograafia võtmetulemus; see on äärmiselt keskne,” ütles Raz. Nullteadmiste tõendit kasutades saab keegi tõestada, et ta krüpteeris või allkirjastas sõnumi õigesti, kasutades oma salavõtit, ilma selle kohta teavet avaldamata. "Avil on krüptograafias mõned äärmiselt olulised tulemused ja see võib olla neist kõige olulisem."

Kuid võib-olla peitub Wigdersoni kõige olulisem tulemus teises valdkonnas: arvutusliku kõvaduse sidumine juhuslikkus. 1970. aastate lõpuks olid arvutiteadlased mõistnud, et paljude raskete probleemide puhul võivad juhuslikkust kasutanud algoritmid, mida nimetatakse ka tõenäosuslikeks algoritmideks, oma deterministlike alternatiividega oluliselt üle konkureerida. Sees 1977 tõendNäiteks Robert Solovay ja Volker Strassen tutvustasid randomiseeritud algoritmi, mis suudab kindlaks teha, kas arv on algarvu kiirem kui tolle aja parimad deterministlikud algoritmid.

Mõne probleemi puhul võivad tõenäosuslikud algoritmid osutada deterministlikele. 1980. aastate alguses töötas Wigderson koos Richard Karpiga California ülikoolist Berkeleys, et seostada juhuslikkuse ideed arvutuslikult rasketeks peetavate probleemidega, mis tähendab, et ükski teadaolev deterministlik algoritm ei suuda neid mõistliku aja jooksul lahendada. "Me ei tea, kuidas tõestada, et nad on rasked," ütles Wigderson. Kuid tema ja Karp leidsid teatud raske probleemi jaoks randomiseeritud algoritmi, mille nad suutsid hiljem derandomiseerida, avastades selle jaoks tõhusalt deterministliku algoritmi. Umbes samal ajal näitasid teised teadlased, kuidas krüptograafiaprobleemide arvutustugevuse eeldused võivad võimaldada derandomiseerimist üldiselt.

Juhuslikkuse ebamõistlik tõhusus pani ta mõtlema juhuslikkuse enda olemusele. Tema, nagu ka teised tollased uurijad, seadis kahtluse alla, kui vajalik on see tõhusaks probleemide lahendamiseks ja millistel tingimustel saab selle üldse kõrvaldada. "Alguses polnud selge, kas see oli ainult meie enda rumalus, et me ei saa juhuslikkust eemaldada," ütles ta. "Kuid suurem küsimus oli, kas juhuslikkust saab alati tõhusalt kõrvaldada või mitte." Ta mõistis, et juhuslikkuse vajadus on tihedalt seotud probleemi arvutusraskustega.

Le 1994 paber, valgustasid tema ja arvutiteadlane Noam Nisan seda seost. Nad tõestasid, et kui esineb looduslikke raskeid probleeme, nagu enamik arvutiteadlasi kahtlustab, saab iga tõhusa randomiseeritud algoritmi asendada tõhusa deterministliku algoritmiga. "Sa võid alati juhuslikkuse kõrvaldada," ütles Wigderson.

Oluline on see, et nad leidsid, et deterministlikud algoritmid võivad kasutada pseudojuhuslikke jadasid - andmejadasid, mis näivad juhuslikud, kuid mitte. Samuti näitasid nad, kuidas raskeid probleeme saab kasutada pseudojuhusliku generaatori ehitamiseks. Pseudojuhuslike bittide (juhuslike bittide asemel) söötmine tõenäosuslikku algoritmi annab sama probleemi jaoks tõhusa deterministliku.

Sudaan ütles, et paber aitas arvutiteadlastel ära tunda juhuslikkuse astmeid, mis võivad aidata paljastada raskete probleemide keerukuse ja nende lahendamise viisid. "See pole lihtsalt juhuslikkus, vaid juhuslikkuse tajumine," ütles ta. "See on võti."

Sudaan juhib tähelepanu sellele, et juhuslikkus näib olevat kõikjal, kuid tegelikult on seda äärmiselt raske leida. "Inimesed ütlevad teile, et pi numbrid näevad välja juhuslikud või algarvude jada tundub juhuslik," ütles ta. "Nad on täiesti kindlameelsed, kuid tunduvad meile juhuslikud." Tema sõnul on juhuslikkuse tajumine tänapäeval arvutiteaduse keskmes. "Ja see on midagi, mida Avi on tohutult edendanud."

Juhuslikkusest on saanud keerukuse teoorias võimas ressurss, kuid see on tabamatu. Wigderson märgib, et mündivisked ja täringuvisked ei ole tõeliselt juhuslikud: kui teil on füüsilise süsteemi kohta piisavalt teavet, on tulemus täiesti etteaimatav. Ta ütles, et täiuslik juhuslikkus on tabamatu ja seda on raske kontrollida.

Kuid Wigersoni jaoks on andmetöötluse näiteid kõikjal - mitte ainult nutitelefonides, sülearvutites ja krüpteerimisalgoritmides, vaid ka bioloogilistes ja füüsilistes süsteemides. Viimastel aastakümnetel on arvutusteooria leiud andnud ülevaate mitmesugustest ootamatutest probleemidest, alates lindude sülemlemisest ja valimistulemustest kuni kehas toimuvate biokeemiliste reaktsioonideni. "Põhimõtteliselt on iga loomulik protsess evolutsioon, mida saate vaadelda arvutustena, nii et saate seda sellisena uurida. Peaaegu kõik arvutab.