Avi Wigderson több mint 40 éve foglalkozik a problémákkal. De mint a számítási komplexitás teoretikusa, nem feltétlenül törődik ezekre a problémákra adott válaszokkal. Gyakran csak azt akarja tudni, hogy megoldhatók-e vagy sem, és hogyan tudja megmondani. „A helyzet nevetséges” – mondta Wigderson, a New Jersey állambeli Princetonban működő Institute for Advanced Study informatikusa. Bármilyen nehéznek is tűnik egy kérdés, a válaszadás hatékony módja lehet, ha elrejtőzik, ha elérhetetlen. „Amennyire tudjuk, minden olyan probléma esetén, amellyel szembesülünk és megpróbáljuk megoldani, nem zárhatjuk ki, hogy van egy algoritmusa, amely meg tudja oldani. Számomra ez a legérdekesebb probléma.”

Ma Wigdersont nevezték ki a győztesnek A.M. Turing-díj, amelyet széles körben a számítástechnika egyik legnagyobb kitüntetésének tartanak, a számításelmélethez való alapvető hozzájárulásáért. Wigderson munkája a terület szinte minden területét érintette. Kollégái, munkatársai és mentoráltjai azt mondják, hogy folyamatosan talál váratlan hidakat a különböző területek között. A véletlenszerűséggel és a számításokkal kapcsolatos munkája pedig az 1990-es években feltárta a matematika és a számítástechnika közötti mély összefüggéseket, amelyek a mai kutatások hátterében állnak.

Madhu Szudán, a Harvard Egyetem informatikusa, aki 2002-ben elnyerte a Rolf Nevanlinna-díjat (jelenleg Abacus-díj), azt mondta, hogy Wigderson befolyását a területre nem lehet figyelmen kívül hagyni. „Nagyon nehéz a számítástechnika bármely területén dolgozni anélkül, hogy Avi munkásságával nem kereszteznénk” – mondta Szudán. "És mindenhol nagyon mély belátásra találsz." Az 1980-as évek végén például Szudán Wigdersonnal dolgozott egy tanulmányon, amely bizonyos matematikai függvények és polinomok közötti összefüggéseket vizsgálta. Ez a munka elindította Szudán egész karrierjét. „Ez jellemző Avira” – mondta Szudán. „Bejut egy térbe, felteszi a megfelelő kérdéseket, majd továbbmegy.”

Wigderson az izraeli Haifában nőtt fel, egy nővér és egy villamosmérnök három fiaként, akik mindketten túlélték a holokausztot. Apja imádta a fejtörőket, és intenzíven érdeklődött a matematika alapvető gondolatai iránt, amelyeket megosztott gyermekeivel. „Ő az a srác, akitől megfertőzött ez a vírus” – mondta Wigderson. Amikor az 1970-es években elkezdte az egyetemet a Haifai Egyetemen, matematikából szeretett volna szakosodni, de szülei informatikára terelték. „Úgy gondolták, talán jó ötlet, hogy lesz munkám, ha végeztem” – mondta.

Talált egy olyan mezőt, amely gazdag mély, megválaszolatlan kérdésekben, amelyek szívében matematikaiak voltak. Egyik legkorábbi úttörő törekvése egy látszólagos ellentmondásra összpontosult: meg lehet-e győzni valakit arról, hogy egy matematikai állítást bebizonyítottak anélkül, hogy megmutatták volna, hogyan.

„Az a személy, aki látja a bizonyítékot, semmit nem tanul magáról a bizonyítékról” – mondta Ran Raz, a Princetoni Egyetem informatikusa. 1985-ben Shafi Goldwasser, Silvio Micali és Charles Rackoff vezette be ezt a koncepciót. zéró tudású interaktív bizonyítások, bemutatva néhány kijelentéshez a használatát. Wigderson, valamint Micali és Oded Goldreich később kifejtette ezt az elképzelést, és lefektette azokat a feltételeket, amelyek azt mutatják, hogy ha egy állítás bizonyítható, zéró tudás igazolása is van.

„Ez kulcsfontosságú eredmény a kriptográfiában; rendkívül központi – mondta Raz. A nulla tudásalapú bizonyítással valaki bebizonyíthatja, hogy megfelelően titkosította vagy aláírta az üzenetet a titkos kulcsával anélkül, hogy bármilyen információt felfedne róla. "Az Avi rendkívül fontos eredményeket ért el a kriptográfiában, és ezek közül talán ez a legfontosabb."

De Wigderson talán legalapvetőbb eredménye egy másik területen rejlik: a számítási keménység összekapcsolásában véletlenszerűség. Az 1970-es évek végére az informatikusok rájöttek, hogy sok nehéz probléma esetén a véletlenszerűséget alkalmazó algoritmusok, más néven valószínűségi algoritmusok nagymértékben felülmúlhatják determinisztikus alternatíváikat. Az a 1977 bizonyítékRobert Solovay és Volker Strassen például bevezetett egy véletlenszerű algoritmust, amely képes meghatározni, hogy egy szám prímszám gyorsabb-e, mint az akkori legjobb determinisztikus algoritmusok.

Egyes problémák esetén a valószínűségi algoritmusok determinisztikusra mutathatnak. Az 1980-as évek elején Wigderson Richard Karppal, a Berkeley-i Kaliforniai Egyetem munkatársával dolgozott azon, hogy összekapcsolja a véletlenszerűség gondolatát a számításilag nehéznek tartott problémákkal, ami azt jelenti, hogy egyetlen ismert determinisztikus algoritmus sem tudja ezeket ésszerű időn belül megoldani. „Nem tudjuk, hogyan bizonyítsuk be, hogy kemények” – mondta Wigderson. Azonban ő és Karp találtak egy randomizált algoritmust egy bizonyos nehéz problémára, amelyet később derandomizálni tudtak, hatékonyan feltárva a determinisztikus algoritmust. Körülbelül ugyanebben az időben más kutatók kimutatták, hogy a kriptográfiai problémák számítási keménységi feltételezései hogyan teszik lehetővé a derandomizálást általában.

A véletlenszerűség ésszerűtlen hatékonysága arra késztette, hogy magának a véletlenszerűségnek a természetéről gondolkodjon. Más kutatókhoz hasonlóan ő is megkérdőjelezte, hogy ez mennyire szükséges a hatékony problémamegoldáshoz, és milyen feltételek mellett lehet teljesen kiküszöbölni. "Kezdetben nem volt világos, hogy ez csak a saját hülyeségünk volt-e, hogy nem tudjuk eltávolítani a véletlenszerűséget" - mondta. "De a nagyobb kérdés az volt, hogy a véletlenszerűség mindig hatékonyan kiküszöbölhető-e vagy sem." Felismerte, hogy a véletlenszerűség iránti igény szorosan összefügg a probléma számítási nehézségével.

Egy 1994 papír, ő és az informatikus Noam Nisan rávilágítottak arra a kapcsolatra. Bebizonyították, hogy ha létezik természetes nehéz probléma, ahogy azt a legtöbb informatikus gyanítja, akkor minden hatékony randomizált algoritmus helyettesíthető egy hatékony determinisztikussal. „A véletlenszerűséget mindig kiküszöbölheti” – mondta Wigderson.

Fontos, hogy azt találták, hogy a determinisztikus algoritmusok „pszeudovéletlen” sorozatokat használhatnak – olyan adatsorokat, amelyek véletlenszerűnek tűnnek, de nem azok. Azt is megmutatták, hogyan lehet bármilyen nehéz feladatot felhasználni egy pszeudovéletlen generátor létrehozására. A pszeudovéletlen bitek (a véletlen bitek helyett) egy valószínűségi algoritmusba való betáplálása hatékony determinisztikus algoritmust eredményez ugyanarra a problémára.

Szudán szerint a papír segített az informatikusoknak felismerni a véletlenszerűség fokozatait, amelyek segíthetnek feltárni a nehéz problémák bonyolultságát és megoldását. "Ez nem csak a véletlenszerűség, hanem a véletlenszerűség észlelése is" - mondta. – Ez a kulcs.

Szudán rámutat, hogy úgy tűnik, hogy a véletlenszerűség mindenhol megjelenik, de valójában rendkívül nehéz megtalálni. „Az emberek azt mondják, hogy a pi számjegyei véletlenszerűnek tűnnek, vagy a prímszámok véletlenszerűek” – mondta. "Teljesen elszántak, de számunkra véletlenszerűnek tűnnek." Szerinte a véletlenszerűség felfogása ma a számítástechnika középpontjában áll. "És ez az, amit Avi hatalmasan népszerűsített."

A véletlenszerűség a komplexitáselmélet erőteljes erőforrásává vált, de megfoghatatlan. Az érmefeldobás és a kockadobás, rámutat Wigderson, nem igazán véletlenszerű: ha elegendő információval rendelkezik a fizikai rendszerről, akkor az eredmény teljesen kiszámítható. A tökéletes véletlenszerűség, mondta, megfoghatatlan, és nehéz ellenőrizni.

Wigerson számára azonban a számítástechnikai példák mindenhol megtalálhatók – nem csak az okostelefonokon és laptopokon és a titkosítási algoritmusokon belül, hanem a biológiai és fizikai rendszerekben is. Az elmúlt évtizedekben a számításelmélet eredményei egy sor váratlan problémába engedtek betekintést, a rajzástól a választási eredményeken át a testben zajló biokémiai reakciókig. „Alapvetően minden természetes folyamat egy evolúció, amelyet számításnak tekinthetünk, tehát úgy is tanulmányozhatjuk. Szinte minden számít.”