I mer enn 40 år har Avi Wigderson studert problemer. Men som beregningskompleksitetsteoretiker bryr han seg ikke nødvendigvis om svarene på disse problemene. Han vil ofte bare vite om de er løsbare eller ikke, og hvordan han kan fortelle. "Situasjonen er latterlig," sa Wigderson, en informatiker ved Institute for Advanced Study i Princeton, New Jersey. Uansett hvor vanskelig et spørsmål virker, kan en effektiv måte å svare på være å gjemme seg rett utenfor rekkevidde. "Så vidt vi vet, for hvert problem vi møter og prøver å løse, kan vi ikke utelukke at det har en algoritme som kan løse det. Dette er det mest interessante problemet for meg.»

I dag ble Wigderson kåret til vinneren av AM Turing-prisen, ansett som en av de beste utmerkelsene innen informatikk, for hans grunnleggende bidrag til teorien om beregning. Wigdersons arbeid har berørt nesten alle områder av feltet. Hans kolleger, samarbeidspartnere og mentees sier at han konsekvent finner uventede broer mellom forskjellige områder. Og hans arbeid med tilfeldighet og beregning, som startet på 1990-tallet, avslørte dype sammenhenger mellom matematikk og informatikk som ligger til grunn for dagens undersøkelser.

Madhu Sudan, en informatiker ved Harvard University som vant Rolf Nevanlinna-prisen i 2002 (nå kalt Abacus-prisen), sa at Wigdersons innflytelse på feltet er umulig å gå glipp av. "Det er veldig vanskelig å jobbe i et hvilket som helst rom innen informatikk uten å faktisk krysse Avis arbeid," sa Sudan. "Og overalt finner du veldig dyp innsikt." På slutten av 1980-tallet jobbet Sudan for eksempel med Wigderson på et papir som undersøkte sammenhenger mellom visse matematiske funksjoner og polynomer. Det arbeidet startet hele Sudans karriere. "Dette er typisk for Avi," sa Sudan. "Han kommer inn i et rom, han stiller de riktige spørsmålene, og så går han videre."

Wigderson vokste opp i Haifa, Israel, som en av tre sønner av en sykepleier og en elektroingeniør, begge overlevende fra Holocaust. Faren hans elsket gåter og var intenst interessert i grunnleggende ideer i matematikk, som han delte med barna sine. "Han er fyren jeg ble infisert av dette viruset fra," sa Wigderson. Da han begynte på college på 1970-tallet, ved Technion i Haifa, ville han ta hovedfag i matematikk, men foreldrene hans styrte ham i stedet til informatikk. "De trodde kanskje det var en god idé at jeg ville ha en jobb når jeg er ferdig," sa han.

Han fant et felt rikt med dype, ubesvarte spørsmål som var matematiske i hjertet. En av hans tidligste banebrytende innsats fokuserte på en tilsynelatende selvmotsigelse: om det var mulig å overbevise noen andre om at et matematisk utsagn var bevist uten å vise hvordan.

"Personen som ser beviset lærer ikke noe om selve beviset," sa Ran Raz, en informatiker ved Princeton University. I 1985 introduserte Shafi Goldwasser, Silvio Micali og Charles Rackoff dette konseptet interaktive bevis med null kunnskap, som demonstrerer bruken for noen få utsagn. Wigderson, sammen med Micali og Oded Goldreich, forklarte senere den ideen, og la ut betingelsene som viser at hvis en uttalelse kan bevises, har også et nullkunnskapsbevis.

«Dette er et nøkkelresultat innen kryptografi; det er ekstremt sentralt, sa Raz. Ved å bruke et nullkunnskapsbevis kan noen bevise at de har kryptert eller signert en melding riktig med sin hemmelige nøkkel, uten å avsløre noen informasjon om det. "Avi har noen ekstremt viktige resultater innen kryptografi, og dette kan være det viktigste av dem."

Men kanskje Wigdersons mest grunnleggende resultat ligger på et annet område: å knytte beregningshardhet til tilfeldig. På slutten av 1970-tallet hadde informatikere innsett at for mange vanskelige problemer kunne algoritmer som brukte tilfeldighet, også kalt probabilistiske algoritmer, utkonkurrere deres deterministiske alternativer. I en 1977 bevis, for eksempel introduserte Robert Solovay og Volker Strassen en randomisert algoritme som kunne avgjøre om et tall er primtall raskere enn datidens beste deterministiske algoritmer.

For noen problemer kan probabilistiske algoritmer peke på deterministiske. På begynnelsen av 1980-tallet jobbet Wigderson sammen med Richard Karp fra University of California, Berkeley, for å koble ideen om tilfeldighet til problemer som anses som vanskelige å regne, noe som betyr at ingen kjente deterministiske algoritmer kan løse dem i løpet av rimelig tid. "Vi vet ikke hvordan vi skal bevise at de er vanskelige," sa Wigderson. Imidlertid fant han og Karp en randomisert algoritme til et visst vanskelig problem som de senere var i stand til å avrandomisere, og effektivt avdekket en deterministisk algoritme for det. Omtrent samtidig viste andre forskere hvordan beregningsmessige hardhetsantakelser i kryptografiske problemer kunne muliggjøre derandomisering generelt.

Den urimelige effektiviteten av tilfeldighet førte til at han tenkte på selve tilfeldighetens natur. Han, som andre forskere på den tiden, stilte spørsmål ved hvor nødvendig det var for effektiv problemløsning og under hvilke forhold det kunne elimineres helt. "I utgangspunktet var det ikke klart om dette bare var vår egen dumhet, at vi ikke kan fjerne tilfeldighet," sa han. "Men det større spørsmålet var om tilfeldighet alltid kan elimineres effektivt eller ikke." Han innså at behovet for tilfeldighet var nært knyttet til beregningsvanskeligheten ved problemet.

For en 1994 papir, han og informatikeren Noam Nisan belyste den forbindelsen. De beviste at hvis det eksisterer noen naturlige harde problemer, som de fleste informatikere mistenker, så kan enhver effektiv randomisert algoritme erstattes av en effektiv deterministisk. "Du kan alltid eliminere tilfeldighet," sa Wigderson.

Viktigere, de fant ut at deterministiske algoritmer kan bruke "pseudotilfeldige" sekvenser - datastrenger som vises tilfeldig, men som ikke er det. De viste også hvordan eventuelle vanskelige problemer kan brukes til å bygge en pseudorandomgenerator. Å mate pseudorandom-bitene (i stedet for de tilfeldige) inn i en sannsynlighetsalgoritme vil resultere i en effektiv deterministisk en for det samme problemet.

Sudan sa at papir hjalp informatikere å gjenkjenne grader av tilfeldighet som kan bidra til å avsløre vanskelighetene ved vanskelige problemer og hvordan de kan løse dem. "Det er ikke bare tilfeldighet, men oppfatninger av tilfeldighet," sa han. "Det er nøkkelen."

Sudan påpeker at tilfeldighet ser ut til å dukke opp overalt, men at det i sannhet er ekstremt vanskelig å finne. "Folk forteller deg at sifrene i pi ser tilfeldige ut, eller sekvensen av tall som er primtall ser tilfeldig ut," sa han. "De er helt bestemte, men de virker tilfeldige for oss." Oppfatningen av tilfeldighet, sa han, ligger i hjertet av informatikk i dag. "Og det er noe som Avi har fremmet enormt."

Tilfeldighet har blitt en kraftig ressurs innen kompleksitetsteori, men det er unnvikende. Myntsving og terningkast, påpeker Wigderson, er ikke virkelig tilfeldige: Hvis du har nok informasjon om det fysiske systemet, så er resultatet helt forutsigbart. Perfekt tilfeldighet, sa han, er unnvikende og vanskelig å verifisere.

Men for Wigerson er eksempler på databehandling overalt - ikke bare innenfor smarttelefoner og bærbare datamaskiner og krypteringsalgoritmer, men også i biologiske og fysiske systemer. De siste tiårene har funn fra beregningsteorien gitt innsikt i en rekke uventede problemer, fra svermerende fugler og valgresultater til biokjemiske reaksjoner i kroppen. "I utgangspunktet er enhver naturlig prosess en evolusjon som du kan se på som beregning, så du kan studere den som sådan. Nesten alt beregnes."