Stel je voor dat je op zoek bent naar de aard van berekeningen. Je bevindt je diep in de wildernis, ver van alle paden, en ondoorgrondelijk berichten zijn uitgehouwen in de stammen van bomen overal om je heen - BPP, AC⁰[m], Σ₂P, YACC en honderden anderen. De glyphs proberen je iets te vertellen, maar waar moet je beginnen? Je kunt ze niet eens allemaal recht houden.

Er zijn maar weinig onderzoekers die zoveel hebben gedaan Russel Impagliazzo om deze schijnbare chaos te doorbreken. Impagliazzo heeft veertig jaar lang voorop gelopen op het gebied van de computationele complexiteitstheorie, de studie van de intrinsieke moeilijkheid van verschillende problemen. De bekendste open vraag op dit gebied, het P versus NP-probleem genoemd, vraagt ​​zich af of veel ogenschijnlijk moeilijke rekenproblemen eigenlijk eenvoudig zijn – met het juiste algoritme. Een antwoord zou verstrekkende gevolgen hebben voor de wetenschap en de veiligheid van de moderne cryptografie.

In de jaren tachtig en negentig speelde Impagliazzo een leidende rol in het verenigen van de wereld. theoretische grondslagen van cryptografie. In 1995 verwoordde hij de betekenis van deze nieuwe ontwikkelingen in een iconisch artikel waarin mogelijke oplossingen voor P versus NP en een handvol gerelateerde problemen opnieuw werden geformuleerd in de taal van vijf hypothetische werelden we zouden kunnen bewonen, grillig genaamd Algorithmica, Heuristica, Pessiland, Minicrypt en Cryptomania. De vijf werelden van Impagliazzo hebben een generatie onderzoekers geïnspireerd, en zij blijven het onderzoek in het bloeiende deelgebied van de wetenschap begeleiden. meta-complexiteit.

En dit zijn niet de enige werelden die hij heeft bedacht. Impagliazzo is al zijn hele leven een liefhebber van rollenspellen op tafel, zoals Dungeons and Dragons, en hij vindt het heerlijk om nieuwe sets regels en nieuwe instellingen om te verkennen. Dezelfde speelse geest bezielt zijn dertig jaar durende praktijk van improvisatiekomedie.

Impagliazzo deed ook fundamenteel werk om de fundamentele rol van willekeur in berekeningen te verduidelijken. Eind jaren zeventig ontdekten computerwetenschappers dat willekeur soms mogelijk is algoritmen verbeteren voor het oplossen van inherent deterministische problemen – een contra-intuïtieve bevinding die onderzoekers jarenlang verbijsterde. Impagliazzo's werk met de complexiteitstheoreticus Avi Wigderson en andere onderzoekers hebben in de jaren negentig aangetoond dat als bepaalde rekenproblemen werkelijk fundamenteel moeilijk zijn, het ook altijd mogelijk om algoritmen die willekeur gebruiken om te zetten in deterministische algoritmen. En omgekeerd, wat bewijst dat willekeur uit elk algoritme kan worden geëlimineerd zou dat ook bewijzen dat er echt moeilijke problemen bestaan.

Quanta sprak met Impagliazzo over het verschil tussen harde problemen en moeilijke puzzels, het raadplegen van orakels en de wiskundige lessen van improvisatiekomedie. Het interview is voor de duidelijkheid ingekort en bewerkt.

Wanneer raakte u voor het eerst geïnteresseerd in wiskunde?

Ik was al geïnteresseerd in wiskunde voordat ik echt wist wat het was. In de derde klas begonnen mijn wiskundecijfers te dalen omdat we de tafels van vermenigvuldiging uit het hoofd moesten leren, en ik weigerde. Mijn moeder zei: "Maar Russell, jij houdt van wiskunde, waarom doe je dit niet?" En ik zei: 'Dat is geen wiskunde, dat is memoriseren. Echte wiskunde houdt geen memoriseren in.” Het enige dat ik op dat moment had geleerd was rekenen, dus ik weet niet zeker waar ik het idee vandaan haalde dat wiskunde over abstracte concepten ging.

Hoe zit het met de informatica? Delen van het vakgebied zijn erg abstract, maar dit is niet wat de meeste mensen voor het eerst tegenkomen.

Op de middelbare school had ik een programmeercursus BASIC gevolgd, maar het was erg moeilijk om iets gedaan te krijgen. De programma's moesten worden overgebracht naar papieren banden, die via deze zeer oude computer moesten worden uitgevoerd, die vaak defect raakte en uw papier in tweeën scheurde. Dus ik dacht dat informatica verschrikkelijk saai was.

Ik was van plan logica te studeren. Maar als je ze daadwerkelijk probeerde te formaliseren, hadden veel van de concepten te maken met berekeningen en vooral met beperkingen op de berekeningen. Vragen als “Hoe weten we dat dingen in de wiskunde waar zijn?” en “Hoe begrijpen we de moeilijkheid van het doen van wiskunde?” leidde tot de theoretische informatica, en in het bijzonder de complexiteitstheorie.

Een deel van uw beroemdste werk onderzoekt de verbanden tussen cryptografie en computationele complexiteitstheorie. Waarom zijn deze twee velden met elkaar verbonden?

Wanneer u een cryptografisch systeem opzet, moet u onderscheid maken tussen legitieme gebruikers (de mensen aan wie u toegang wilt verlenen) en alle anderen. Computationeel moeilijke problemen bieden ons een manier om deze groepen te onderscheiden op basis van wat ze weten. Maar als je wilt dat het antwoord op een probleem een ​​manier is om twee groepen mensen van elkaar te onderscheiden, kun je niet zomaar een moeilijk probleem gebruiken; je hebt een moeilijke puzzel nodig.

Wat is het verschil tussen een probleem en een puzzel?

Over het algemeen weet de persoon die een probleem stelt het antwoord misschien niet. Een puzzel is een probleem dat is ontworpen met een antwoord in gedachten. Dus waarom hebben we een puzzel nodig? Omdat we moeten kunnen vaststellen of iemand die het zogenaamd heeft opgelost, dat ook daadwerkelijk heeft gedaan. In het dagelijks leven gebruiken we puzzels ter vermaak, maar we gebruiken ze ook in de klas om te testen of mensen de stof begrepen. Dit is wat er gebeurt in cryptografie: we gebruiken puzzels om iemands kennis te testen.

Het verschil tussen de vijf werelden is de manier waarop zij de vragen ‘Zijn er moeilijke problemen?’ beantwoorden. en “Zijn er moeilijke puzzels?”

Hoe komen die verschillende antwoorden tot stand?

In de eerste wereld, Algorithmica, zijn geen problemen moeilijk. Je hoeft niet te weten hoe iemand je probleem heeft ontworpen: je kunt het altijd oplossen. Heuristica zegt: "Nou, misschien zijn een paar problemen moeilijk." Dan komen we in Pessiland, waar veel problemen moeilijk zijn, maar de meeste puzzels niet. Bijna elk probleem dat ik verzin en waarvan ik de oplossing weet, zul jij ook kunnen oplossen. Al deze werelden zijn slecht voor cryptografie.

In Minicrypt kan ik puzzels maken waarvan ik weet hoe ik ze moet oplossen, maar die nog steeds erg uitdagend voor je zijn. En ten slotte is Cryptomania een wereld waarin twee mensen op een openbare locatie kunnen staan ​​waar een afluisteraar het kan horen en samen een puzzel kunnen maken die voor de afluisteraar nog moeilijk is.

Wat motiveerde u om de vijf wereldenkrant te schrijven?

Destijds was bekend dat verschillende antwoorden op de P- versus NP-vraag een grote impact zouden hebben op wat voor soort problemen we kunnen oplossen en ook op wat voor soort veiligheid we kunnen hopen. Maar het kwalitatieve onderscheid tussen verschillende vormen van gemak en hardheid waren niet echt duidelijk.

Slechts een paar jaar eerder was er een zeer verhelderend artikel waarin de verschillen werden uiteengezet met behulp van veel onderling samenhangende vragen met zo'n twintig mogelijke antwoorden. Eén reden waarom ik de vijfwereldenkrant wilde schrijven, was dat we in die paar jaar enorm veel vooruitgang hadden geboekt. Het zou moeilijk zijn geweest om namen te vinden voor twintig mogelijke werelden.

Dus waarom zou je het zo framen, als verschillende werelden met eigenzinnige namen?

Ik had ermee ingestemd dit artikel voor een conferentie te schrijven. Ik bleef 's avonds laat op om erachter te komen wat ik ging zeggen, en ergens rond één uur 's nachts leek het een goed idee om de verschillende werelden in te kaderen. En toen las ik het de volgende ochtend en het leek nog steeds een prima idee – het was een manier om te laten zien hoe deze ideeën de wereld daadwerkelijk zouden beïnvloeden zonder verstrikt te raken in kwantitatieve details. Wat mij het gelukkigst maakt aan dit artikel is dat ik van mensen die onderzoek doen naar complexiteit hoor dat dit het artikel was dat hen als studenten in het vakgebied interesseerde.

Hebben onderzoekers een van de vijf mogelijke werelden uitgesloten?

We voegen er eigenlijk meer toe – waar mensen over beginnen te praten Obfustopie als een wereld van nog sterkere cryptografische hulpmiddelen. Het is een beetje deprimerend dat we eind jaren tachtig zoveel vooruitgang hebben geboekt en sindsdien geen enkele wereld meer hebben geëlimineerd. Maar aan de andere kant weten we veel meer over de verbindingen tussen werelden en hebben we een veel duidelijker beeld van hoe elke wereld eruit zou zien.

Hypothetische werelden spelen ook een andere rol in de complexiteitstheorie, in bewijzen die het bestaan ​​van ‘orakels’ veronderstellen. Dus, allereerst, wat is een orakel precies?

Stel je voor dat iemand een ingenieus apparaat bouwt dat een probleem kan oplossen, zonder dat we een algoritme kennen om dat probleem op te lossen. Dat is wat een orakel is. Als we zo'n wonderbaarlijk apparaat zouden hebben en het in onze computers zouden stoppen, zou het kunnen verschuiven waar de grens ligt tussen wat berekenbaar is en wat niet berekenbaar is.

Denken onderzoekers dat deze magische dozen echt kunnen bestaan?

Nee, waarschijnlijk bestaan ​​ze niet. In het begin waren de orakelresultaten enigszins controversieel omdat ze zo hypothetisch waren. Maar één manier waarop ze heel verhelderend kunnen zijn, is wanneer het orakel wordt gebruikt om een ​​ideale situatie te modelleren. Stel dat je probeert aan te tonen dat A niet noodzakelijkerwijs B impliceert. Je begint met de setting waar je de meest extreme A hebt en laat zien dat dat nog steeds niet genoeg is om B te garanderen. Als je kunt aantonen dat zelfs als alle kansen gelijk zijn in jouw voordeel kun je iets nog steeds niet bewijzen, dat is echt een sterk bewijs dat het moeilijk te bewijzen zal zijn.

Je hebt ook verbanden ontdekt tussen rekenhardheid en willekeur. Hoe werkt die verbinding?

Het is eigenlijk een manier om te zeggen dat als je iets niet begrijpt, het misschien willekeurig lijkt. Stel dat ik zeg dat ik aan een getal tussen één en duizend denk. Als ik het getal willekeurig kies, heb je een kans van één op duizend om het te raden. En als ik – in navolging van Monty Python – vraag: “Wat is in mijlen per uur de gemiddelde luchtsnelheid van een Europese zwaluw?” je hebt ongeveer dezelfde kans. Het gaat waarschijnlijk meer dan één mijl per uur, en waarschijnlijk niet meer dan duizend mijl per uur.

Dit is eigenlijk niet willekeurig; het is een deterministisch te beantwoorden vraag. We zouden gewoon alle zwaluwen kunnen meten die rondvliegen, maar dat is nogal moeilijk te bepalen met beperkte middelen, zoals het ontbreken van een budget voor het meten van de sliksnelheden en het niet hebben van een oneindige voorraad zwaluwen.

Het inzicht is dus dat moeilijke problemen waarvan we de oplossingen niet kennen, een bron kunnen vormen van “pseudo-willekeurige” getallen die er willekeurig uitzien.

Over Monty Python gesproken, ik weet dat je al heel lang met improvisatiecomedy bezig bent. Hoe ben je begonnen?

Ik begon als assistent-professor in San Diego in 1991. En rond '94 of zo dacht ik: "Ik heb echt niet veel leven buiten de afdeling." Dus kreeg ik de gratis weekkrant en bladerde ik door de lijst met clubs en activiteiten. Ik heb alles geëlimineerd behalve improvisatiekomedie - ik dacht dat het op zijn minst aannemelijk was dat ik er goed in zou zijn. Ik ontmoette mijn vrouw in die beginnersklas.

Wat dacht ze?

Ze zegt dat ik echt verschrikkelijk was. Als je een logicus bent, ben je getraind om altijd na te denken over de nuance van elk woord. Je wilt niet iets verkeerds zeggen. Improvisatie is geweldig omdat het het omgekeerde doet: het gaat er niet om iets perfects te zeggen, maar om snel iets te verzinnen. Het was het tegenovergestelde van de rest van mijn leven.

Mijn huidige vrouw nam een ​​pauze van de les, en toen ze een jaar later terugkwam, slaagde ik erin indruk op haar te maken. Dat was 30 jaar geleden. Ik volg nog steeds dezelfde les bij dezelfde instructeur.

Heeft improvisatie de manier veranderd waarop u uw onderzoek benadert?

Het is een goede gewoonte om niet hyperkritisch te zijn over elke gedachte die je hebt. Dat is vooral handig bij samenwerkingen. Als ik met andere mensen werkte, zei ik dingen als: 'Maar dat idee werkt niet om de volgende reden. Dat is niet letterlijk waar.” Bij improvisatie wordt er altijd van je verwacht dat je accepteert wat je partner zegt. En ik denk dat dat een goede houding is, vooral als je onderzoek doet met studenten: wijs iets wat ze zeggen niet af alleen maar omdat je weet dat het niet klopt. Er zijn veel goede ideeën die niet 100% correct zijn.

Zoals?

Als je intuïtie voor een probleem probeert te krijgen, kan het helpen om te beginnen met een aantal vereenvoudigende aannames. Deze aannames zijn meestal niet waar, maar ze kunnen u helpen bij het opstellen van een routekaart. Zeg: 'Als ik een olifant had, zou ik over de bergen kunnen komen. Natuurlijk heb ik geen olifant. Maar als ik dat deed, dan is dit hoe ik het zou doen.” En dan besef je: “Nou, misschien heb ik voor deze stap geen olifant nodig. Een muilezel zou prima zijn.”

Hoe zit het met uw liefde voor rollenspellen? Heeft dat uw werk überhaupt beïnvloed?

Het heeft misschien niet al mijn onderzoek beïnvloed, maar het heeft zeker wel mijn vijfwereldenpaper beïnvloed. Ik heb altijd een algemene interesse gehad in fantasy en science fiction en het bedenken van verschillende mogelijke werelden – hoe zouden de dingen zijn als alles anders was?

Waarom zijn rollenspellen zo’n aantrekkelijke manier om hypothetische werelden te verkennen?

Mensen die van speculatieve fictie houden, hebben altijd werelden uitgevonden. Tolkien is er het meest bekend om, en hij had zo'n enorme verbeeldingskracht dat zijn wereld echt geleefd voelde. Voor degenen onder ons die niet zo fantasierijk zijn: de beste manier om dat te bereiken is door mensen uit te nodigen in je omgeving en een spel te spelen. is een manier om dat te doen. Nu is het niet alleen mijn wereld. Het is misschien begonnen zoals ik het me had voorgesteld, maar net als bij elke samenwerking is het dankzij de bijdragen van iedereen al ver voorbij dat niveau geëvolueerd.