Avi Wigderson, pionier op het gebied van de complexiteitstheorie, wint Turing Award | Quanta-tijdschrift

Al meer dan 40 jaar bestudeert Avi Wigderson problemen. Maar als computationele complexiteitstheoreticus bekommert hij zich niet noodzakelijkerwijs om de antwoorden op deze problemen. Vaak wil hij gewoon weten of ze oplosbaar zijn of niet, en hoe hij dat kan vertellen. “De situatie is belachelijk”, zei hij Wigderson, een computerwetenschapper aan het Institute for Advanced Study in Princeton, New Jersey. Hoe moeilijk een vraag ook lijkt, een efficiënte manier om deze te beantwoorden kan zich net buiten bereik verbergen. “Voor zover we weten, kunnen we voor elk probleem waarmee we worden geconfronteerd en dat we proberen op te lossen, niet uitsluiten dat er een algoritme voor bestaat dat het probleem kan oplossen. Dit is voor mij het meest interessante probleem.”

Vandaag werd Wigderson uitgeroepen tot winnaar van de AM Turing-prijs, algemeen beschouwd als een van de hoogste onderscheidingen in de informatica, vanwege zijn fundamentele bijdragen aan de berekeningstheorie. Wigdersons werk heeft bijna elk gebied van het vakgebied geraakt. Zijn collega's, medewerkers en leerlingen zeggen dat hij voortdurend onverwachte bruggen vindt tussen uiteenlopende gebieden. En zijn werk over willekeur en berekeningen, dat in de jaren negentig begon, bracht diepe verbanden aan het licht tussen wiskunde en informatica die ten grondslag liggen aan het huidige onderzoek.

Madhu Soedan, een computerwetenschapper aan de universiteit van Harvard die in 2002 de Rolf Nevanlinna-prijs won (nu de Abacus-prijs genoemd), zei dat Wigdersons invloed op het veld onmogelijk te missen is. "Het is heel moeilijk om op welk gebied dan ook in de informatica te werken zonder daadwerkelijk te kruisen met het werk van Avi," zei Sudan. “En overal vind je hele diepe inzichten.” Eind jaren tachtig werkte Sudan bijvoorbeeld samen met Wigderson aan een artikel waarin verbanden tussen bepaalde wiskundige functies en polynomen werden onderzocht. Dat werk lanceerde de hele carrière van Soedan. “Dit is typisch voor Avi”, zei Sudan. "Hij komt in de ruimte, stelt de juiste vragen en gaat dan verder."

Wigderson groeide op in Haifa, Israël, als een van de drie zonen van een verpleegster en een elektrotechnisch ingenieur, beiden overlevenden van de Holocaust. Zijn vader hield van puzzels en was intens geïnteresseerd in fundamentele ideeën in de wiskunde, die hij met zijn kinderen deelde. “Hij is de man van wie ik door dit virus ben besmet”, zei Wigderson. Toen hij in de jaren zeventig aan de Technion in Haifa ging studeren, wilde hij wiskunde als hoofdvak studeren, maar zijn ouders stuurden hem in plaats daarvan naar informatica. 'Ze dachten dat het misschien een goed idee was dat ik een baan zou hebben als ik klaar ben', zei hij.

Hij vond een vakgebied dat rijk was aan diepgaande, onbeantwoorde vragen met een wiskundig karakter. Een van zijn eerste baanbrekende inspanningen concentreerde zich op een schijnbare tegenstrijdigheid: of het mogelijk was iemand anders ervan te overtuigen dat een wiskundige bewering bewezen was zonder te laten zien hoe.

"De persoon die het bewijs ziet, leert niets over het bewijs zelf", zei hij Ran Razo, een computerwetenschapper aan de Universiteit van Princeton. In 1985 introduceerden Shafi Goldwasser, Silvio Micali en Charles Rackoff dit concept van zero-knowledge interactieve bewijzen, waarmee het gebruik ervan voor een paar uitspraken wordt gedemonstreerd. Wigderson heeft dit idee later, samen met Micali en Oded Goldreich, uiteengezet en de voorwaarden uiteengezet die aantonen dat als een verklaring kan worden bewezen, deze ook kan worden bewezen. heeft ook een nulkennisbewijs.

“Dit is een belangrijk resultaat in cryptografie; het is extreem centraal,” zei Raz. Met behulp van een zero-knowledge proof kan iemand bewijzen dat hij een bericht correct heeft gecodeerd of ondertekend met zijn geheime sleutel, zonder dat er enige informatie over wordt prijsgegeven. “Avi heeft een aantal uiterst belangrijke resultaten geboekt op het gebied van cryptografie, en dit is misschien wel de belangrijkste.”

Maar misschien ligt het meest fundamentele resultaat van Wigderson op een ander gebied: het koppelen van rekenhardheid aan willekeurigheid. Tegen het einde van de jaren zeventig hadden computerwetenschappers zich gerealiseerd dat voor veel moeilijke problemen algoritmen die gebruik maakten van willekeur, ook wel probabilistische algoritmen genoemd, hun deterministische alternatieven ruimschoots konden overtreffen. In een 1977-bestendigRobert Solovay en Volker Strassen introduceerden bijvoorbeeld een gerandomiseerd algoritme dat sneller kon bepalen of een getal een priemgetal is dan de beste deterministische algoritmen van die tijd.

Voor sommige problemen kunnen probabilistische algoritmen verwijzen naar deterministische algoritmen. Begin jaren tachtig werkte Wigderson samen met Richard Karp van de Universiteit van Californië, Berkeley, om het idee van willekeur te verbinden met problemen die als computationeel moeilijk werden beschouwd, wat betekent dat geen bekende deterministische algoritmen ze binnen een redelijke tijd kunnen oplossen. 'We weten niet hoe we moeten bewijzen dat ze moeilijk zijn,' zei Wigderson. Hij en Karp vonden echter een gerandomiseerd algoritme voor een bepaald moeilijk probleem dat ze later konden derandomiseren, waardoor er effectief een deterministisch algoritme voor werd ontdekt. Rond dezelfde tijd lieten andere onderzoekers zien hoe aannames van computationele hardheid bij cryptografieproblemen derandomisatie in het algemeen mogelijk zouden kunnen maken.

De onredelijke effectiviteit van willekeur bracht hem ertoe na te denken over de aard van willekeur zelf. Net als andere onderzoekers uit die tijd vroeg hij zich af hoe noodzakelijk het was voor een efficiënte probleemoplossing en onder welke omstandigheden het helemaal geëlimineerd kon worden. “Aanvankelijk was het niet duidelijk of dit alleen onze eigen domheid was, dat we de willekeur niet kunnen wegnemen”, zei hij. “Maar de grotere vraag was of willekeur altijd efficiënt kan worden geëlimineerd of niet.” Hij realiseerde zich dat de behoefte aan willekeur nauw verbonden was met de rekenmoeilijkheid van het probleem.

Voor een 1994 papier, lichtten hij en de computerwetenschapper Noam Nisan dat verband toe. Ze bewezen dat als er natuurlijke harde problemen bestaan, zoals de meeste computerwetenschappers vermoeden, elk efficiënt gerandomiseerd algoritme kan worden vervangen door een efficiënt deterministisch algoritme. “Je kunt willekeur altijd elimineren”, zei Wigderson.

Belangrijk is dat ze ontdekten dat deterministische algoritmen ‘pseudowillekeurige’ reeksen kunnen gebruiken: reeksen gegevens die willekeurig lijken, maar dat niet zijn. Ze lieten ook zien hoe harde problemen kunnen worden gebruikt om een ​​pseudo-willekeurige generator te bouwen. Het invoeren van de pseudo-willekeurige bits (in plaats van de willekeurige) in een probabilistisch algoritme zal resulteren in een efficiënt deterministisch algoritme voor hetzelfde probleem.

Sudan zei dat papier computerwetenschappers hielp de mate van willekeur te herkennen die kon helpen de complexiteit van harde problemen bloot te leggen en hoe deze op te lossen. "Het is niet alleen willekeur, maar percepties van willekeur", zei hij. “Dat is de sleutel.”

Sudan wijst erop dat willekeur overal lijkt te voorkomen, maar in werkelijkheid uiterst moeilijk te vinden is. “Mensen vertellen je dat de cijfers van pi er willekeurig uitzien, of dat de reeks priemgetallen er willekeurig uitziet,” zei hij. “Ze zijn volkomen vastberaden, maar voor ons lijken ze willekeurig.” De perceptie van willekeur vormt volgens hem de kern van de hedendaagse computerwetenschap. “En dat is iets dat Avi enorm heeft gepromoot.”

Willekeur is een krachtig hulpmiddel geworden in de complexiteitstheorie, maar het is ongrijpbaar. Het opgooien van munten en het gooien van dobbelstenen is volgens Wigderson niet echt willekeurig: als je voldoende informatie hebt over het fysieke systeem, is het resultaat volkomen voorspelbaar. Perfecte willekeur, zei hij, is ongrijpbaar en moeilijk te verifiëren.

Maar volgens Wigerson zijn er overal voorbeelden van computergebruik – niet alleen in smartphones en laptops en encryptie-algoritmen, maar ook in biologische en fysieke systemen. De afgelopen decennia hebben bevindingen uit de rekentheorie inzichten opgeleverd in een reeks onverwachte problemen, van zwermen vogels en verkiezingsresultaten tot biochemische reacties in het lichaam. “In principe is elk natuurlijk proces een evolutie die je kunt zien als een berekening, dus je kunt het ook als zodanig bestuderen. Bijna alles wordt berekend.”