Tenk deg at du er på et oppdrag for å forstå selve naturen til beregning. Du er dypt inne i villmarken, langt fra noen stier, og uutgrunnelig meldinger er skåret inn i stammene til trærne rundt deg - BPP, AC⁰[m], Σ₂P, YACC og hundrevis av andre. Tegnene prøver å fortelle deg noe, men hvor skal du begynne? Du kan ikke engang holde dem alle rett.

Få forskere har gjort så mye som Russell Impagliazzo å kutte gjennom dette tilsynelatende kaoset. I 40 år har Impagliazzo jobbet i spissen for beregningskompleksitetsteori, studiet av den iboende vanskeligheten til forskjellige problemer. Det mest kjente åpne spørsmålet på dette feltet, kalt P versus NP-problemet, spør om mange tilsynelatende vanskelige beregningsproblemer faktisk er enkle - med riktig algoritme. Et svar ville ha vidtrekkende implikasjoner for vitenskapen og sikkerheten til moderne kryptografi.

På 1980- og 1990-tallet spilte Impagliazzo en ledende rolle i å forene teoretiske grunnlag for kryptografi. I 1995 artikulerte han betydningen av disse nye utviklingene i en ikonisk artikkel som omformulerte mulige løsninger på P versus NP og en håndfull relaterte problemer på språket til fem hypotetiske verdener vi kan bebo, lunefullt kalt Algorithmica, Heuristica, Pessiland, Minicrypt og Cryptomania. Impagliazzos fem verdener har inspirert en generasjon forskere, og de fortsetter å veilede forskning i det blomstrende delfeltet av metakompleksitet.

Og dette er ikke de eneste verdenene han har drømt om. Impagliazzo har vært en livslang tilhenger av bordrollespill som Dungeons and Dragons, og han gleder seg over å finne opp nye sett med regler og nye innstillinger å utforske. Den samme lekne ånden animerer hans 30-årige praksis med improvisasjonskomedie.

Impagliazzo gjorde også grunnleggende arbeid for å belyse den grunnleggende rollen til tilfeldighet i beregninger. På slutten av 1970-tallet oppdaget dataforskere at tilfeldighet noen ganger kunne forbedre algoritmer for å løse iboende deterministiske problemer - et kontraintuitivt funn som forvirret forskere i årevis. Impagliazzos arbeid med kompleksitetsteoretikeren Avi Wigderson og andre forskere på 1990-tallet viste at hvis visse beregningsproblemer virkelig er grunnleggende vanskelige, så er det alltid mulig å konvertere algoritmer som bruker tilfeldighet til deterministiske. Og omvendt, beviser at tilfeldighet kan elimineres fra enhver algoritme ville også bevise at det virkelig finnes vanskelige problemer.

Quanta snakket med Impagliazzo om forskjellen mellom vanskelige problemer og harde gåter, rådgivende orakler og de matematiske leksjonene til improkomedie. Intervjuet er komprimert og redigert for klarhet.

Når ble du først interessert i matematikk?

Jeg var interessert i matematikk selv før jeg egentlig visste hva det var. I tredje klasse begynte mattekarakterene mine å skli fordi vi skulle lære multiplikasjonstabellene våre utenat, og jeg nektet. Moren min sa: "Men Russell, du elsker matematikk, hvorfor gjør du ikke dette?" Og jeg sa: «Det er ikke matematikk, det er memorering. Ekte matematikk involverer ikke memorering.» Alt jeg hadde lært på det tidspunktet var aritmetikk, så jeg er ikke sikker på hvor jeg fikk forestillingen om at matematikk handlet om abstrakte begreper.

Hva med informatikk? Deler av feltet er veldig abstrakte, men det er ikke det folk flest møter først.

På videregående hadde jeg hatt et programmeringskurs i BASIC, men det var veldig vanskelig å få til noe. Programmene måtte overføres til papirbånd, som måtte kjøres gjennom denne svært gamle datamaskinen som ofte feilet og rev papiret ditt i to. Så jeg syntes informatikk var fryktelig kjedelig.

Jeg hadde tenkt å studere logikk. Men mange av konseptene, når du prøvde å faktisk formalisere dem, involverte beregning og spesielt begrensninger for beregning. Spørsmål som "Hvordan vet vi at ting i matematikk er sanne?" og "Hvordan forstår vi vanskelighetene med å gjøre matematikk?" førte til teoretisk informatikk, og kompleksitetsteori spesielt.

Noen av de mest kjente verkene dine utforsker sammenhengene mellom kryptografi og beregningskompleksitetsteori. Hvorfor er disse to feltene relatert?

Når du setter opp et kryptografisk system, må du skille mellom legitime brukere – personene du vil gi tilgang til – og alle andre. Beregningsmessig vanskelige problemer gir oss en måte å skille disse gruppene på basert på hva de vet. Men hvis du vil at svaret på et problem skal være en måte å skille to grupper av mennesker på, kan du ikke bare bruke et hvilket som helst vanskelig problem - du trenger et hardt puslespill.

Hva er forskjellen mellom et problem og et puslespill?

Generelt kan det hende at personen som utgjør et problem ikke vet svaret. Et puslespill er et problem designet med et svar i tankene. Så hvorfor trenger vi et puslespill? Fordi vi må kunne avgjøre om en person som visstnok løste det faktisk gjorde det. I hverdagen bruker vi puslespill til moro, men vi bruker dem også i klasserom for å teste om folk forsto stoffet. Dette er hva som skjer i kryptografi: Vi bruker gåter for å teste noens kunnskap.

Forskjellen mellom de fem verdenene er hvordan de svarer på spørsmålene "Er det vanskelige problemer?" og "Finnes det vanskelige gåter?"

Hvordan spiller de forskjellige svarene ut?

I den første verden, Algorithmica, er ingen problemer vanskelig. Du trenger ikke vite hvordan noen utformet problemet ditt: Du kan alltid løse det. Heuristica sier: "Vel, kanskje noen problemer er vanskelige." Så kommer vi til Pessiland, hvor mange problemer er vanskelige, men de fleste gåtene er det ikke. Nesten alle problemer jeg finner på der jeg vet løsningen, vil du også kunne løse det. Alle disse verdenene er dårlige for kryptografi.

I Minicrypt kan jeg lage gåter som jeg vet hvordan jeg skal løse som fortsatt er veldig utfordrende for deg. Og til slutt, Cryptomania er en verden der to personer kan stå på et offentlig sted der en avlytter kan høre og sammen skape et puslespill som fortsatt er vanskelig for avlytteren.

Hva motiverte deg til å skrive de fem verdener papir?

På den tiden var det kjent at ulike svar på P versus NP-spørsmålet ville ha stor innvirkning på hva slags problemer vi kan løse og også hva slags sikkerhet vi kan håpe på, men de kvalitative skillene mellom ulike former for letthet og hardheten var ikke helt klar.

Det var en veldig innsiktsfull artikkel bare noen år tidligere som la ut forskjellene ved å bruke mange sammenhengende spørsmål med omtrent 20 mulige svar. En grunn til at jeg ønsket å skrive femverdener-avisen var at vi hadde gjort store fremskritt på disse få årene. Det ville vært vanskelig å finne navn for 20 mulige verdener.

Så hvorfor ramme det på den måten, som forskjellige verdener med sære navn?

Jeg hadde sagt ja til å skrive denne artikkelen for en konferanse. Jeg var oppe til sent på kvelden og prøvde å finne ut hva jeg skulle si, og et sted rundt klokken 1 virket innramming av forskjellige verdener som en god idé. Og så leste jeg det neste morgen, og det virket fortsatt som en OK idé - det var en måte å vise hvordan disse ideene faktisk ville påvirke verden uten å bli fanget opp i kvantitative detaljer. Det som gjør meg mest glad med denne artikkelen er at jeg hører fra folk som forsker i kompleksitet at dette var papiret som fikk dem til å interessere seg for feltet som studenter.

Har forskere utelukket noen av de fem mulige verdenene?

Vi legger faktisk til flere - folk har begynt å snakke om Obfustopi som en verden av enda sterkere kryptografiske verktøy. Det er litt deprimerende at vi gjorde så mye fremgang på slutten av 1980-tallet og ikke har eliminert noen verdener siden den gang. Men på den annen side vet vi mye mer om sammenhengene mellom verdener og har en mye klarere bilde hvordan hver verden ville se ut.

Hypotetiske verdener spiller også en annen rolle i kompleksitetsteori, i bevis som antar eksistensen av "orakler". Så, først av alt, hva er egentlig et orakel?

Tenk deg at noen bygger en genial enhet som kan løse et eller annet problem uten at vi kjenner en algoritme for å løse det problemet. Det er det et orakel er. Hvis vi hadde en slik mirakuløs enhet og vi satt den inne i datamaskinene våre, kunne den endret hvor linjen går mellom hva som er beregnet og hva som ikke kan beregnes.

Tror forskerne at disse magiske boksene faktisk kan eksistere?

Nei, de finnes nok ikke. Tidlig var orakelresultatene noe kontroversielle fordi de er så hypotetiske. Men en måte de kan være veldig opplysende på er når oraklet brukes til å modellere en ideell situasjon. Si at du prøver å vise at A ikke nødvendigvis innebærer B. Du starter med innstillingen der du har den mest ekstreme A og viser at det fortsatt ikke er nok til å garantere B. Hvis du kan vise det selv om alle odds er til din fordel kan du fortsatt ikke bevise noe, det er virkelig sterke bevis på at det kommer til å bli vanskelig å bevise.

Du har også oppdaget sammenhenger mellom beregningshardhet og tilfeldighet. Hvordan fungerer den forbindelsen?

Det er egentlig en måte å si at hvis du ikke forstår noe, så kan det virke tilfeldig. Anta at jeg sier at jeg tenker på et tall mellom én og tusen. Hvis jeg velger tallet tilfeldig, har du en sjanse på én til tusen til å gjette det. Og hvis jeg spør – etter Monty Python – «I miles per time, hva er gjennomsnittshastigheten for en europeisk svale?» du har omtrent samme sjanse. Den går sannsynligvis mer enn én mil i timen, og den går sannsynligvis ikke mer enn tusen kilometer i timen.

Dette er faktisk ikke tilfeldig - det er et deterministisk svar på spørsmål. Vi kunne bare måle alle svalene som flyr rundt, men det er litt vanskelig å bestemme med begrensede ressurser, som å ikke ha et budsjett for å måle svelgehastigheter og ikke ha en uendelig tilførsel av sveler.

Så innsikten er at vanskelige problemer hvis løsninger vi ikke kjenner kan gi en kilde til "pseudotilfeldige" tall som ser tilfeldige ut.

Apropos Monty Python, jeg vet at du har drevet med impro-komedie i lang tid nå – hvordan kom du i gang?

Jeg begynte som assisterende professor i San Diego i 1991. Og rundt 94 eller så tenkte jeg: «Jeg har egentlig ikke mye av et liv utenfor avdelingen.» Så jeg fikk den gratis ukeavisen, og jeg så gjennom listen over klubber og aktiviteter. Jeg eliminerte alt bortsett fra improkomedie - jeg trodde det i det minste var sannsynlig at jeg ville klare det. Jeg møtte kona mi i den nybegynnerklassen.

Hva tenkte hun?

Hun sier jeg var virkelig forferdelig. Når du er en logiker, er du opplært til å alltid tenke på nyansen til hvert ord. Du vil ikke si noe feil. Improv er flott ved at det snur det: Poenget er ikke å si noe perfekt, men å finne på noe raskt. Det var det motsatte av resten av livet mitt.

Min nåværende kone tok en pause fra timen, og da hun kom tilbake et år senere, klarte jeg å imponere henne. Det var for 30 år siden. Jeg tar fortsatt samme time med samme instruktør.

Har improvisasjon endret måten du tilnærmer deg forskningen din?

Det er god praksis for ikke å være hyperkritisk til alle tanker du har. Det er spesielt nyttig i samarbeid. Når jeg jobbet med andre mennesker, pleide jeg å si ting som: «Men den ideen vil ikke fungere av følgende grunn. Det er ikke bokstavelig talt sant." I improvisasjon skal du alltid akseptere det partneren din sier. Og det synes jeg er en god holdning å ha, spesielt når du forsker med studenter: Ikke avvis noe de sier bare fordi du vet at det er feil. Det er mange gode ideer som ikke er 100% riktige.

Som hva?

Når du prøver å få intuisjon for et problem, er en ting som hjelper å starte med noen forenklede antakelser. Disse antakelsene er vanligvis ikke sanne, men de kan hjelpe deg med å komme opp med et veikart. Si: «Hvis jeg hadde en elefant, kunne jeg komme meg over fjellene. Selvfølgelig har jeg ingen elefant. Men hvis jeg gjorde det, her er hvordan jeg ville gjort det.» Og så skjønner du: «Vel, kanskje jeg ikke trenger en elefant for dette trinnet. Et muldyr ville vært fint."

Hva med din kjærlighet til rollespill – har det i det hele tatt påvirket arbeidet ditt?

Det kan ikke ha påvirket all forskningen min, men den påvirket absolutt min fem verdener-artikkel. Jeg har alltid hatt en generell interesse for fantasy og science fiction og komme opp med forskjellige mulige verdener - hvordan ville ting vært hvis alt var annerledes?

Hvorfor er rollespill en så overbevisende måte å utforske hypotetiske verdener på?

Folk som er interessert i spekulativ fiksjon har alltid oppfunnet verdener. Tolkien er mest kjent for det, og han hadde en så massiv fantasi at verden hans faktisk føltes levd i. For de av oss som ikke er like fantasifulle, er den beste måten å oppnå det på å invitere folk inn i miljøet ditt, og et spill er en måte å gjøre det på. Nå er det ikke bare min verden. Det kan ha startet slik jeg forestilte meg det, men akkurat som i ethvert samarbeid, på grunn av alle andres bidrag, har det utviklet seg langt forbi det.