Föreställ dig att du är på jakt efter att förstå själva beräkningens natur. Du är djupt inne i vildmarken, långt ifrån alla stigar, och outgrundlig meddelanden är uthuggna i trädstammarna runt omkring dig - BPP, AC⁰[m], Σ₂P, YACC och hundratals andra. Glyferna försöker säga dig något, men var ska du börja? Du kan inte ens hålla dem alla raka.

Få forskare har gjort så mycket som Russell Impagliazzo att skära igenom detta till synes kaos. I 40 år har Impagliazzo arbetat i framkant av beräkningskomplexitetsteorin, studiet av den inneboende svårigheten hos olika problem. Den mest kända öppna frågan inom detta område, kallad P versus NP-problemet, frågar om många till synes svåra beräkningsproblem faktiskt är lätta - med rätt algoritm. Ett svar skulle få långtgående konsekvenser för vetenskapen och säkerheten för modern kryptografi.

På 1980- och 1990-talen spelade Impagliazzo en ledande roll i att förena teoretiska grunder för kryptografi. 1995 artikulerade han betydelsen av dessa nya utvecklingar i en ikonisk artikel som omformulerade möjliga lösningar på P kontra NP och en handfull relaterade problem på språket fem hypotetiska världar vi kanske bor, nyckfullt kallade Algorithmica, Heuristica, Pessiland, Minicrypt och Cryptomania. Impagliazzos fem världar har inspirerat en generation av forskare, och de fortsätter att vägleda forskning inom det blomstrande delområdet metakomplexitet.

Och det här är inte de enda världarna han har drömt om. Impagliazzo har varit en livslång avicionado av bordsrollspel som Dungeons and Dragons, och han njuter av att uppfinna nya uppsättningar regler och nya inställningar att utforska. Samma lekfulla anda animerar hans 30-åriga praktik av improvisationskomedi.

Impagliazzo gjorde också grundläggande arbete för att klargöra den grundläggande rollen av slumpmässighet i beräkningar. I slutet av 1970-talet upptäckte datavetare att slumpmässighet ibland kunde förbättra algoritmer för att lösa inneboende deterministiska problem - ett kontraintuitivt fynd som förbryllat forskare i flera år. Impagliazzos arbete med komplexitetsteoretikern Avi Wigderson och andra forskare på 1990-talet visade att om vissa beräkningsproblem verkligen är fundamentalt svåra, så är det alltid möjligt att omvandla algoritmer som använder slumpmässighet till deterministiska. Och omvänt bevisar att slumpmässighet kan elimineras från vilken algoritm som helst skulle också bevisa att det verkligen finns svåra problem.

Quanta pratade med Impagliazzo om skillnaden mellan svåra problem och svåra pussel, konsulterande orakel och de matematiska lärdomarna av improviserad komedi. Intervjun har förtätats och redigerats för tydlighetens skull.

När började du intressera dig för matematik för första gången?

Jag var intresserad av matematik redan innan jag riktigt visste vad det var. I tredje klass började mina mattebetyg halka eftersom vi skulle memorera våra multiplikationstabeller, och jag vägrade. Min mamma sa: "Men Russell, du älskar matematik, varför gör du inte det här?" Och jag sa: ”Det är inte matematik, det är memorering. Verklig matematik involverar inte memorering.” Allt jag hade lärt mig vid den tidpunkten var aritmetik, så jag är inte säker på var jag fick uppfattningen att matematik handlade om abstrakta begrepp.

Hur är det med datavetenskap? Delar av fältet är mycket abstrakta, men de är inte vad de flesta människor först möter.

På gymnasiet hade jag gått en programmeringskurs i BASIC, men det var verkligen svårt att få något gjort. Programmen var tvungna att överföras till pappersband, som måste köras genom denna mycket gamla dator som ofta misslyckades och slet ditt papper på mitten. Så jag tyckte att datavetenskap var fruktansvärt tråkigt.

Jag tänkte studera logik. Men många av begreppen, när man försökte formalisera dem, involverade beräkning och särskilt begränsningar för beräkning. Frågor som "Hur vet vi att saker i matematik är sanna?" och "Hur förstår vi svårigheten att göra matematik?" ledde till teoretisk datavetenskap, och speciellt komplexitetsteori.

Några av dina mest kända verk utforskar kopplingarna mellan kryptografi och beräkningskomplexitetsteori. Varför är dessa två områden relaterade?

När du ställer in ett kryptografiskt system måste du skilja mellan legitima användare – de personer du vill ge åtkomst till – och alla andra. Beräkningssvåra problem ger oss ett sätt att särskilja dessa grupper utifrån vad de vet. Men om du vill att svaret på ett problem ska vara ett sätt att särskilja två grupper av människor, kan du inte bara använda vilket svårt problem som helst – du behöver ett hårt pussel.

Vad är skillnaden mellan ett problem och ett pussel?

I allmänhet kanske den som ställer ett problem inte vet svaret. Ett pussel är ett problem utformat med ett svar i åtanke. Så varför behöver vi ett pussel? För vi måste kunna avgöra om en person som ska ha löst det faktiskt gjorde det. I vardagen använder vi pussel för att roa oss, men vi använder dem också i klassrummen för att testa om folk förstod materialet. Detta är vad som händer i kryptografi: Vi använder pussel för att testa någons kunskap.

Skillnaden mellan de fem världarna är hur de svarar på frågorna "Finns det svåra problem?" och "Finns det svåra pussel?"

Hur ser de olika svaren ut?

I den första världen, Algorithmica, är inga problem svåra. Du behöver inte veta hur någon utformade ditt problem: du kan alltid lösa det. Heuristica säger: "Tja, några problem kanske är svåra." Sedan kommer vi till Pessiland, där många problem är svåra, men de flesta pussel är det inte. Nästan alla problem som jag hittar på där jag vet lösningen, du kommer att kunna lösa det också. Alla dessa världar är dåliga för kryptografi.

I Minicrypt kan jag skapa pussel som jag vet hur jag ska lösa som fortfarande är riktigt utmanande för dig. Och slutligen, Cryptomania är en värld där två personer kan stå på en offentlig plats där en avlyssnare kan höra och tillsammans skapa ett pussel som fortfarande är svårt för avlyssnaren.

Vad motiverade dig att skriva de fem världarnas papper?

På den tiden var det känt att olika svar på P kontra NP-frågan skulle ha stor inverkan på vilken typ av problem vi kan lösa och även vilken typ av säkerhet vi kan hoppas på, men de kvalitativa distinktionerna mellan olika former av lätthet och hårdheten var inte riktigt tydlig.

Det fanns ett mycket insiktsfullt papper bara några år tidigare som lade ut distinktionerna med hjälp av många inbördes relaterade frågor med ungefär 20 möjliga svar. En anledning till att jag ville skriva fem världars uppsats var att vi hade gjort enorma framsteg under dessa få år. Det skulle ha varit svårt att hitta namn på 20 möjliga världar.

Så varför rama in det på det sättet, som olika världar med konstiga namn?

Jag hade tackat ja till att skriva detta papper för en konferens. Jag satt uppe sent på natten och försökte komma på vad jag skulle säga, och någonstans runt 1 verkade inramningen av olika världar vara en bra idé. Och sedan läste jag det nästa morgon och det verkade fortfarande som en OK idé - det var ett sätt att visa hur dessa idéer faktiskt skulle påverka världen utan att fastna i kvantitativa detaljer. Det som gör mig gladast med den här uppsatsen är att jag hör från folk som forskar i komplexitet att detta var uppsatsen som fick dem att intressera sig för området som studenter.

Har forskare uteslutit någon av de fem möjliga världarna?

Vi lägger faktiskt till fler — folk har börjat prata om Obfustopi som en värld av ännu starkare kryptografiska verktyg. Det är lite deprimerande att vi gjorde så mycket framsteg i slutet av 1980-talet och inte har eliminerat några världar sedan dess. Men å andra sidan vet vi mycket mer om sambanden mellan världar och har en mycket tydligare bild hur varje värld skulle se ut.

Hypotetiska världar spelar också en annan roll i komplexitetsteorin, i bevis som antar existensen av "orakel". Så, först och främst, vad är egentligen ett orakel?

Föreställ dig att någon bygger en genialisk enhet som kan lösa något problem utan att vi känner till en algoritm för att lösa det problemet. Det är vad ett orakel är. Om vi ​​hade en sådan mirakulös enhet och vi stoppade in den i våra datorer, skulle den kunna flyttas var gränsen går mellan vad som är beräkningsbart och vad som inte är beräkningsbart.

Tror forskarna att dessa magiska lådor verkligen kan existera?

Nej, de finns nog inte. Tidigt var orakelresultaten något kontroversiella eftersom de är så hypotetiska. Men ett sätt de kan vara mycket upplysande är när oraklet används för att modellera en ideal situation. Säg att du försöker visa att A inte nödvändigtvis innebär B. Du börjar med den inställning där du har det mest extrema A och visar att det fortfarande inte räcker för att garantera B. Om du kan visa det även om alla odds är till din fördel kan du fortfarande inte bevisa något, det är verkligen starka bevis på att det kommer att bli svårt att bevisa.

Du har också upptäckt kopplingar mellan beräkningshårdhet och slumpmässighet. Hur fungerar den kopplingen?

Det är verkligen ett sätt att säga att om du inte förstår något så kan det verka slumpmässigt. Anta att jag säger att jag tänker på en siffra mellan ett och tusen. Om jag väljer numret slumpmässigt har du en chans på en på tusen att gissa det. Och om jag frågar – efter Monty Python – "I miles per hour, vad är den genomsnittliga flyghastigheten för en europeisk svala?" du har ungefär samma chans. Det går förmodligen mer än en mil i timmen, och det går förmodligen inte mer än tusen mil i timmen.

Detta är faktiskt inte slumpmässigt - det är en deterministiskt besvarbar fråga. Vi skulle bara kunna mäta alla svalor som flyger runt, men det är lite svårt att avgöra med begränsade resurser, som att inte ha en budget för att mäta svalans hastigheter och att inte ha ett oändligt utbud av svalor.

Så insikten är att svåra problem vars lösningar vi inte känner till kan ge en källa till "pseudoslumpmässiga" siffror som ser slumpmässiga ut.

På tal om Monty Python, jag vet att du har gjort improvkomedi länge nu – hur kom du igång?

Jag började som biträdande professor i San Diego 1991. Och runt 94 eller så tänkte jag: "Jag har verkligen inte så mycket liv utanför institutionen." Så jag fick veckotidningen gratis, och jag tittade igenom listan över klubbar och aktiviteter. Jag eliminerade allt utom improkomedi - jag trodde att det åtminstone var rimligt att jag skulle klara det. Jag träffade min fru i den där nybörjarklassen.

Vad tyckte hon?

Hon säger att jag var riktigt hemsk. När du är logiker är du tränad att alltid tänka på nyansen i varje ord. Du vill inte säga något felaktigt. Improv är bra genom att det vänder på det: Poängen är inte att säga något perfekt utan att hitta på något snabbt. Det var motsatsen till resten av mitt liv.

Min nu fru tog en paus från klassen och när hon kom tillbaka ett år senare lyckades jag imponera på henne. Det var 30 år sedan. Jag går fortfarande i samma klass med samma instruktör.

Har improvisation förändrat ditt sätt att närma dig din forskning?

Det är bra att inte vara hyperkritisk när det gäller varje tanke du har. Det är särskilt användbart i samarbeten. När jag arbetade med andra människor brukade jag säga saker som: "Men den idén kommer inte att fungera av följande anledning. Det är inte bokstavligen sant." I improvisation ska du alltid acceptera vad din partner säger. Och det tycker jag är en bra inställning att ha, speciellt när du forskar med elever: Avfärda inte något de säger bara för att du vet att det är felaktigt. Det finns många bra idéer som inte är 100% korrekta.

Som vad?

När du försöker få intuition för ett problem är en sak som hjälper att börja med några förenklade antaganden. Dessa antaganden är vanligtvis inte sanna, men de kan hjälpa dig att ta fram en färdplan. Säg: "Om jag hade en elefant skulle jag kunna ta mig över bergen. Självklart har jag ingen elefant. Men om jag gjorde det, så här skulle jag göra det.” Och då inser du, "Ja, jag kanske inte behöver en elefant för det här steget. En mula skulle vara bra."

Hur är det med din kärlek till rollspel – har det påverkat ditt arbete överhuvudtaget?

Det kanske inte har påverkat all min forskning, men det påverkade verkligen min fem världar uppsats. Jag har alltid haft ett allmänt intresse för fantasy och science fiction och att komma på olika möjliga världar – hur skulle det se ut om allt var annorlunda?

Varför är rollspel ett så övertygande sätt att utforska hypotetiska världar?

Människor som gillar spekulativ fiktion har alltid uppfunnit världar. Tolkien är mest känd för det, och han hade en så enorm fantasi att hans värld faktiskt kändes levd i. För de av oss som inte är lika fantasifulla är det bästa sättet att uppnå det att bjuda in människor till din miljö och ett spel är ett sätt att göra det. Nu är det inte bara min värld. Det kan ha börjat som jag föreställde mig det, men precis som i alla samarbeten, på grund av alla andras bidrag, har det utvecklats långt förbi det.