Avi Wigderson on tutkinut ongelmia yli 40 vuoden ajan. Mutta laskennallisen monimutkaisuuden teoreetikona hän ei välttämättä välitä vastauksista näihin ongelmiin. Hän usein haluaa vain tietää, ovatko ne ratkaistavissa vai eivät, ja kuinka kertoa. "Tilanne on naurettava", sanoi Wigderson, tietojenkäsittelytieteilijä Institute for Advanced Studyssa Princetonissa, New Jerseyssä. Riippumatta siitä, kuinka vaikealta kysymys näyttää, tehokas tapa vastata siihen voisi olla piiloutuminen ulottumattomiin. ”Sikäli kuin tiedämme, emme voi sulkea pois jokaista kohtaamaamme ja ratkaistavaamme ongelmaa, että sillä on algoritmi, joka voi ratkaista sen. Tämä on minulle kiinnostavin ongelma."

Tänään Wigderson nimettiin voittajaksi AM Turing -palkinto, jota pidetään laajalti yhtenä tietojenkäsittelytieteen suurimmista kunnianosoituksista hänen perustavanlaatuisesta panoksestaan ​​laskentateoriassa. Wigdersonin työ on koskettanut lähes kaikkia alan alueita. Hänen kollegansa, yhteistyökumppaninsa ja mentoroitavansa sanovat, että hän löytää jatkuvasti odottamattomia siltoja erilaisten alueiden välillä. Ja hänen satunnaisuutta ja laskemista koskeva työnsä 1990-luvulta lähtien paljasti syvät yhteydet matematiikan ja tietojenkäsittelytieteen välillä, jotka ovat tämän päivän tutkimusten taustalla.

Madhu Sudan, Harvardin yliopiston tietojenkäsittelytieteilijä, joka voitti vuoden 2002 Rolf Nevanlinna -palkinnon (nykyään Abacus-palkinnon), sanoi, että Wigdersonin vaikutusta alalla on mahdotonta jättää huomiotta. "On erittäin vaikeaa työskennellä missä tahansa tietojenkäsittelytieteen alalla ilman, että se on ristiriidassa Avin työn kanssa", Sudan sanoi. "Ja kaikkialta löydät erittäin syvällisiä oivalluksia." Esimerkiksi 1980-luvun lopulla Sudan työskenteli Wigdersonin kanssa paperilla, jossa tutkittiin tiettyjen matemaattisten funktioiden ja polynomien välisiä yhteyksiä. Tämä työ käynnisti Sudanin koko uran. "Tämä on tyypillistä Aville", sanoi Sudan. "Hän pääsee johonkin tilaan, hän kysyy oikeat kysymykset ja sitten jatkaa eteenpäin."

Wigderson varttui Haifassa Israelissa yhtenä kolmesta sairaanhoitajan ja sähköinsinöörin pojasta, jotka molemmat selvisivät holokaustista. Hänen isänsä rakasti pulmia ja oli erittäin kiinnostunut matematiikan perusideoista, joita hän jakoi lapsilleen. "Hän on se kaveri, josta sain tämän viruksen tartunnan", Wigderson sanoi. Kun hän aloitti yliopisto-opinnot 1970-luvulla Haifan yliopistossa, hän halusi pääaineenaan matematiikkaa, mutta hänen vanhempansa ohjasivat hänet tietotekniikan pariin. "He ajattelivat, että ehkä oli hyvä idea, että minulla olisi työpaikka, kun olen valmis", hän sanoi.

Hän löysi kentän, joka oli täynnä syviä, vastaamattomia kysymyksiä, jotka olivat pohjimmiltaan matemaattisia. Yksi hänen varhaisimmista uraauurtavista ponnisteluistaan ​​keskittyi näennäiseen ristiriitaisuuteen: oliko mahdollista saada joku muu vakuuttuneeksi siitä, että matemaattinen väite oli todistettu näyttämättä miten.

"Ihminen, joka näkee todisteen, ei opi mitään itse todistuksesta", sanoi Ran Raz, tietojenkäsittelytieteilijä Princetonin yliopistosta. Vuonna 1985 Shafi Goldwasser, Silvio Micali ja Charles Rackoff esittelivät tämän käsitteen nolla-tietoa interaktiivisia todisteita, joka osoittaa sen käytön muutamassa lausunnossa. Wigderson yhdessä Micalin ja Oded Goldreichin kanssa selittivät myöhemmin tätä ajatusta ja esittivät ehdot, jotka osoittavat, että jos väite voidaan todistaa, se sillä on myös nollatietotodistus.

"Tämä on keskeinen tulos kryptografiassa; se on erittäin keskeinen”, Raz sanoi. Nollatietotodisteen avulla joku voi todistaa salaaneensa tai allekirjoittaneensa viestin oikein salaisella avaimellaan paljastamatta siitä mitään tietoja. "Avilla on erittäin tärkeitä tuloksia kryptografiassa, ja tämä saattaa olla niistä tärkein."

Mutta ehkä Wigdersonin perustavanlaatuisin tulos on toisella alueella: laskennallisen kovuuden yhdistäminen satunnaisuuden. 1970-luvun lopulla tietojenkäsittelytieteilijät olivat ymmärtäneet, että monissa vaikeissa ongelmissa satunnaisuutta käyttävät algoritmit, joita kutsutaan myös todennäköisyysalgoritmeiksi, voivat kilpailla huomattavasti determinististen vaihtoehtojensa kanssa. Jonkin sisällä 1977-todisteEsimerkiksi Robert Solovay ja Volker Strassen esittelivät satunnaistetun algoritmin, joka pystyi määrittämään, onko luku alkuluku nopeampi kuin sen ajan parhaat deterministiset algoritmit.

Joissakin ongelmissa todennäköisyyspohjaiset algoritmit voivat osoittaa deterministisiä. 1980-luvun alussa Wigderson työskenteli Richard Karpin kanssa Kalifornian yliopistosta Berkeleystä yhdistääkseen satunnaisuuden ajatuksen laskennallisesti vaikeina pidettyihin ongelmiin, mikä tarkoittaa, että mitkään tunnetut deterministiset algoritmit eivät pysty ratkaisemaan niitä kohtuullisessa ajassa. "Emme tiedä kuinka todistaa, että he ovat kovia", Wigderson sanoi. Hän ja Karp löysivät kuitenkin satunnaistetun algoritmin tiettyyn vaikeaan ongelmaan, jonka he pystyivät myöhemmin derandomisoimaan, paljastaen tehokkaasti sille deterministisen algoritmin. Samaan aikaan muut tutkijat osoittivat, kuinka salausongelmien laskennalliset kovuusoletukset voisivat mahdollistaa derandomisoinnin yleensä.

Satunnaisuuden kohtuuton tehokkuus sai hänet ajattelemaan itse satunnaisuuden luonnetta. Hän, kuten muutkin tutkijat tuolloin, kyseenalaisti sen tarpeellisuuden tehokkaalle ongelmanratkaisulle ja millä ehdoilla se voitaisiin poistaa kokonaan. "Aluksi ei ollut selvää, oliko tämä vain omaa tyhmyyttämme, ettemme voi poistaa satunnaisuutta", hän sanoi. "Mutta suurempi kysymys oli, voidaanko satunnaisuus aina poistaa tehokkaasti vai ei." Hän ymmärsi, että satunnaisuuden tarve oli kiinteästi sidoksissa ongelman laskennalliseen vaikeuteen.

Jotta 1994 paperi, hän ja tietojenkäsittelytieteilijä Noam Nisan valasivat tätä yhteyttä. He osoittivat, että jos luonnollisia vaikeita ongelmia on olemassa, kuten useimmat tietotekniikan tutkijat epäilevät, jokainen tehokas satunnaistettu algoritmi voidaan korvata tehokkaalla deterministisellä algoritmilla. "Voit aina poistaa satunnaisuuden", Wigderson sanoi.

Tärkeää on, että he havaitsivat, että deterministiset algoritmit voivat käyttää "pseudosatunnaisia" sekvenssejä - tietojonoja, jotka näyttävät satunnaisilta, mutta eivät ole. He myös osoittivat, kuinka mitä tahansa vaikeita ongelmia voidaan käyttää näennäissatunnaisen generaattorin rakentamiseen. Näennäissatunnaisten bittien syöttäminen (satunnaisten bittien sijaan) todennäköisyysalgoritmiin johtaa tehokkaaseen deterministiseen samaan ongelmaan.

Sudan sanoi, että paperi auttoi tietotekniikan tutkijoita tunnistamaan satunnaisuuden asteita, jotka voisivat auttaa paljastamaan vaikeiden ongelmien monimutkaisuudet ja niiden ratkaisemisen. "Se ei ole vain satunnaisuutta, vaan havaintoja satunnaisuudesta", hän sanoi. "Se on avain."

Sudan huomauttaa, että satunnaisuus näyttää näkyvän kaikkialla, mutta sitä on itse asiassa erittäin vaikea löytää. "Ihmiset sanovat, että pi:n numerot näyttävät satunnaisilta tai alkulukujen sarja näyttää satunnaiselta", hän sanoi. "He ovat täysin päättäväisiä, mutta meistä ne näyttävät sattumanvaraisilta." Hänen mukaansa satunnaisuuden käsitys on tämän päivän tietojenkäsittelytieteen ytimessä. "Ja se on jotain, jota Avi on edistänyt valtavasti."

Satunnaisuudesta on tullut voimakas resurssi monimutkaisuusteoriassa, mutta se on vaikeasti havaittavissa. Wigderson huomauttaa, että kolikonheitot ja nopanheitot eivät ole todella satunnaisia: Jos sinulla on tarpeeksi tietoa fyysisestä järjestelmästä, tulos on täysin ennustettavissa. Täydellinen satunnaisuus on hänen mukaansa vaikeasti todennettavissa.

Mutta Wigersonille esimerkkejä tietojenkäsittelystä on kaikkialla - ei vain älypuhelimissa ja kannettavissa tietokoneissa ja salausalgoritmeissa, vaan myös biologisissa ja fyysisissä järjestelmissä. Viime vuosikymmeninä laskentateorian havainnot ovat tuoneet käsitystä moniin odottamattomiin ongelmiin lintujen parveilusta ja vaalien tuloksista kehon biokemiallisiin reaktioihin. ”Periaatteessa mikä tahansa luonnollinen prosessi on evoluutiota, jota voit tarkastella laskennalla, joten voit tutkia sitä sellaisenaan. Melkein kaikki laskee.”