Avi Wigderson, Complexity Theory Pioneer, vinner Turing Award | Quanta Magazine

I mer än 40 år har Avi Wigderson studerat problem. Men som beräkningskomplexitetsteoretiker bryr han sig inte nödvändigtvis om svaren på dessa problem. Han vill ofta bara veta om de är lösbara eller inte, och hur han ska berätta. "Situationen är löjlig," sa Wigderson, en datavetare vid Institute for Advanced Study i Princeton, New Jersey. Oavsett hur svår en fråga verkar, kan ett effektivt sätt att besvara den vara att gömma sig precis utom räckhåll. "Såvitt vi vet, för varje problem som vi möter och försöker lösa, kan vi inte utesluta att det har en algoritm som kan lösa det. Det här är det enskilt mest intressanta problemet för mig.”

Idag utsågs Wigderson till vinnare av AM Turing Award, allmänt ansedd som en av de främsta utmärkelserna inom datavetenskap, för sina grundläggande bidrag till teorin om beräkning. Wigdersons arbete har berört nästan alla områden på området. Hans kollegor, medarbetare och adepter säger att han konsekvent hittar oväntade broar mellan olika områden. Och hans arbete med slumpmässighet och beräkning, som började på 1990-talet, avslöjade djupa kopplingar mellan matematik och datavetenskap som ligger till grund för dagens undersökningar.

Madhu Sudan, en datavetare vid Harvard University som vann Rolf Nevanlinna-priset 2002 (nu kallat Abacus-priset), sa att Wigdersons inflytande på fältet är omöjligt att missa. "Det är väldigt svårt att arbeta i vilket utrymme som helst inom datavetenskap utan att faktiskt korsa Avis arbete," sade Sudan. "Och överallt hittar du mycket djupa insikter." I slutet av 1980-talet, till exempel, arbetade Sudan med Wigderson på ett papper som undersökte sambanden mellan vissa matematiska funktioner och polynom. Det arbetet startade Sudans hela karriär. "Detta är typiskt för Avi," sa Sudan. "Han kommer in i ett utrymme, han ställer de rätta frågorna och sedan går han vidare."

Wigderson växte upp i Haifa, Israel, som en av tre söner till en sjuksköterska och en elektroingenjör, båda överlevande från Förintelsen. Hans far älskade pussel och var intensivt intresserad av grundläggande idéer inom matematik, som han delade med sina barn. "Han är killen från vilken jag blev infekterad av det här viruset," sa Wigderson. När han började på college på 1970-talet, vid Technion i Haifa, ville han gå in i matematik som huvudämne, men hans föräldrar styrde honom istället till datavetenskap. "De tyckte att det kanske var en bra idé att jag skulle ha ett jobb när jag är klar", sa han.

Han fann ett fält rikt med djupa, obesvarade frågor som var matematiska i grunden. En av hans tidigaste banbrytande insatser fokuserade på en till synes motsägelse: om det var möjligt att övertyga någon annan om att ett matematiskt påstående hade bevisats utan att visa hur.

"Den person som ser beviset lär sig ingenting om själva beviset," sa Sprang Raz, en datavetare vid Princeton University. 1985 introducerade Shafi Goldwasser, Silvio Micali och Charles Rackoff detta koncept av noll-kunskap interaktiva bevis, som visar dess användning för några påståenden. Wigderson, tillsammans med Micali och Oded Goldreich, förklarade senare den idén och lade upp villkoren som visar att om ett påstående kan bevisas, har också ett nollkunskapsbevis.

”Detta är ett nyckelresultat inom kryptografi; det är extremt centralt”, sa Raz. Med hjälp av ett noll-kunskapsbevis kan någon bevisa att de korrekt krypterade eller signerade ett meddelande med sin hemliga nyckel, utan att avslöja någon information om det. "Avi har några extremt viktiga resultat inom kryptografi, och det här kan vara det viktigaste av dem."

Men Wigdersons kanske mest grundläggande resultat ligger inom ett annat område: att koppla beräkningshårdhet till slumpmässighet. I slutet av 1970-talet hade datavetare insett att för många svåra problem kunde algoritmer som använde slumpmässighet, även kallade probabilistiska algoritmer, i hög grad konkurrera ut sina deterministiska alternativ. I en 1977-bevis, till exempel introducerade Robert Solovay och Volker Strassen en randomiserad algoritm som kunde avgöra om ett tal är primtal snabbare än den tidens bästa deterministiska algoritmer.

För vissa problem kan probabilistiska algoritmer peka på deterministiska. I början av 1980-talet arbetade Wigderson med Richard Karp från University of California, Berkeley, för att koppla idén om slumpmässighet till problem som anses vara beräkningssvåra, vilket innebär att inga kända deterministiska algoritmer kan lösa dem inom en rimlig tid. "Vi vet inte hur vi ska bevisa att de är svåra," sa Wigderson. Men han och Karp hittade en randomiserad algoritm för ett visst svårt problem som de senare kunde avrandomisera, vilket effektivt avslöjade en deterministisk algoritm för det. Ungefär samtidigt visade andra forskare hur antaganden om beräkningshårdhet i kryptografiska problem kunde möjliggöra derandomisering i allmänhet.

Den orimliga effektiviteten av slumpmässighet fick honom att tänka på själva slumpmässighetens natur. Han, liksom andra forskare på den tiden, ifrågasatte hur nödvändigt det var för effektiv problemlösning och under vilka förutsättningar det kunde elimineras helt. "Inledningsvis var det inte klart om detta bara var vår egen dumhet, att vi inte kan ta bort slumpmässighet," sa han. "Men den större frågan var om slumpmässighet alltid kan elimineras effektivt eller inte." Han insåg att behovet av slumpmässighet var intimt kopplat till problemets beräkningssvårigheter.

För en 1994 papper, belyste han och datavetaren Noam Nisan den kopplingen. De bevisade att om det finns några naturliga svåra problem, som de flesta datavetare misstänker, så kan varje effektiv randomiserad algoritm ersättas med en effektiv deterministisk. "Du kan alltid eliminera slumpmässighet," sa Wigderson.

Viktigt, de fann att deterministiska algoritmer kan använda "pseudoslumpmässiga" sekvenser - strängar av data som verkar slumpmässiga men inte är det. De visade också hur alla svåra problem kan användas för att bygga en pseudoslumpgenerator. Att mata de pseudoslumpmässiga bitarna (istället för de slumpmässiga) till en probabilistisk algoritm kommer att resultera i en effektiv deterministisk för samma problem.

Sudan sa att papper hjälpte datavetare att känna igen grader av slumpmässighet som kunde hjälpa till att avslöja svårigheterna med svåra problem och hur man löser dem. "Det är inte bara slumpmässighet utan uppfattningar om slumpmässighet," sa han. "Det är nyckeln."

Sudan påpekar att slumpmässighet verkar förekomma överallt men är i sanning extremt svår att hitta. "Folk säger till dig att siffrorna i pi ser slumpmässiga ut, eller sekvensen av tal som är primtal ser slumpmässigt ut," sa han. "De är helt bestämda, men de verkar slumpmässiga för oss." Uppfattningen om slumpmässighet, sa han, ligger i hjärtat av datavetenskap idag. "Och det är något som Avi har främjat enormt."

Slumpmässighet har blivit en kraftfull resurs inom komplexitetsteorin, men det är svårfångat. Myntslag och tärningskast, påpekar Wigderson, är inte riktigt slumpmässiga: Om du har tillräckligt med information om det fysiska systemet är resultatet helt förutsägbart. Perfekt slumpmässighet, sa han, är svårfångad och svår att verifiera.

Men för Wigerson finns exempel på datoranvändning överallt - inte bara inom smartphones och bärbara datorer och krypteringsalgoritmer utan också i biologiska och fysiska system. Under de senaste decennierna har fynd från teorin om beräkning gett insikter i en rad oväntade problem, från svärmande fåglar och valresultat till biokemiska reaktioner i kroppen. "I grund och botten är vilken naturlig process som helst en evolution som du kan se som beräkning, så du kan studera den som sådan. Nästan allt räknas."