Kuvittele, että yrität ymmärtää laskennan luonteen. Olet syvällä erämaassa, kaukana kaikista poluista ja tutkimaton viestien on kaiverrettu ympärilläsi olevien puiden runkoihin – BPP, AC⁰[m], Σ₂P, YACC ja sadat muut. Glyfit yrittävät kertoa sinulle jotain, mutta mistä aloittaa? Et voi edes pitää niitä kaikkia suoraan.

Harvat tutkijat ovat tehneet niin paljon kuin Russell Impagliazzo leikkaamaan tämän näennäisen kaaoksen läpi. Impagliazzo on työskennellyt 40 vuoden ajan laskennallisen monimutkaisuuden teorian, eri ongelmien luontaisen vaikeuden tutkimuksen, eturintamassa. Tämän alan tunnetuin avoin kysymys, nimeltään P vs. NP -ongelma, kysyy, ovatko monet näennäisesti vaikeat laskennalliset ongelmat todella helppoja - oikealla algoritmilla. Vastauksella olisi kauaskantoisia vaikutuksia tieteeseen ja nykyaikaisen kryptografian turvallisuuteen.

1980- ja 1990-luvuilla Impagliazzo oli johtavassa asemassa kryptografian teoreettiset perusteet. Vuonna 1995 hän ilmaisi näiden uusien kehityssuuntien merkityksen ikonisessa paperissa, joka muotoili uudelleen mahdolliset ratkaisut P vastaan ​​NP ja kourallinen niihin liittyviä ongelmia. viisi hypoteettista maailmaa saatamme asua, omituisesti nimitettyinä Algorithmica, Heuristica, Pessiland, Minicrypt ja Cryptomania. Impagliazzon viisi maailmaa ovat inspiroineet tutkijoiden sukupolvea, ja ne ohjaavat edelleen tutkimusta kukoistavalla ala-alalla. meta-monimutkaisuus.

Ja nämä eivät ole ainoita maailmoja, joista hän on haaveillut. Impagliazzo on ollut elinikäinen pöytäroolipelien, kuten Dungeons and Dragons, fani, ja hän nauttii keksimisestä uusia sääntöjä ja uusia asetuksia tutkittavaksi. Sama leikkisä henki elävöittää hänen 30 vuoden improvisaatiokomedian harjoittelua.

Impagliazzo teki myös perustavaa työtä selvittäessään satunnaisuuden perustavanlaatuista roolia laskennassa. 1970-luvun lopulla tietotekniikan tutkijat havaitsivat, että satunnaisuus voi joskus olla parantaa algoritmeja luontaisesti determinististen ongelmien ratkaisemiseen – intuitiivinen havainto, joka hämmentyi tutkijoita vuosia. Impagliazzon työ kompleksisuusteoreetikon kanssa Avi Wigderson ja muut tutkijat 1990-luvulla osoittivat, että jos tietyt laskennalliset ongelmat ovat pohjimmiltaan vaikeita, se on aina mahdollista muuntaa satunnaisuutta käyttävät algoritmit deterministisiksi. Ja päinvastoin, todistetaan, että satunnaisuus voidaan eliminoida mistä tahansa algoritmista myös todistaisi että todella vaikeita ongelmia on olemassa.

Quanta puhui Impagliazzon kanssa kovien ongelmien ja kovien pulmien eroista, oraakkeleista ja improkomedian matemaattisista opetuksista. Haastattelu on tiivistetty ja muokattu selvyyden vuoksi.

Milloin kiinnostuit ensimmäisen kerran matematiikasta?

Kiinnostuin matematiikasta jo ennen kuin tiesin, mitä se oli. Kolmannella luokalla matematiikan arvosanani alkoivat lipsua, koska meidän piti opetella kertotaulukkomme ulkoa, ja kieltäydyin. Äitini sanoi: "Mutta Russell, sinä rakastat matematiikkaa, miksi et tee tätä?" Ja minä sanoin: "Se ei ole matematiikkaa, se on ulkoa oppimista. Todellinen matematiikka ei sisällä ulkoa opiskelua." Olin oppinut tuolloin vain aritmetiikkaa, joten en ole varma, mistä sain käsityksen, että matematiikka koski abstrakteja käsitteitä.

Entä tietojenkäsittelytiede? Alan osat ovat hyvin abstrakteja, mutta ne eivät ole sitä, mitä useimmat ihmiset kohtaavat ensimmäisen kerran.

Lukiossa minulla oli BASIC-ohjelmointikurssi, mutta oli todella vaikeaa saada mitään aikaan. Ohjelmat piti siirtää paperinauhoille, jotka piti ajaa tämän hyvin vanhan tietokoneen läpi, joka usein epäonnistui ja repi paperisi kahtia. Joten ajattelin tietojenkäsittelytieteen olevan hirvittävän tylsää.

Ajattelin opiskella logiikkaa. Mutta monet käsitteet, kun yritit formalisoida niitä, sisälsivät laskennan ja erityisesti laskennan rajoitukset. Kysymykset, kuten "Mistä tiedämme, että matematiikassa on totta?" ja "Kuinka ymmärrämme matematiikan tekemisen vaikeuden?" johti teoreettiseen tietojenkäsittelytieteeseen ja erityisesti monimutkaisuusteoriaan.

Jotkut kuuluisimmista teoksistasi tutkivat salauksen ja laskennallisen monimutkaisuuden teorian välisiä yhteyksiä. Miksi nämä kaksi alaa liittyvät toisiinsa?

Kun asennat salausjärjestelmää, sinun on erotettava lailliset käyttäjät – ihmiset, joille haluat myöntää käyttöoikeuden – ja kaikki muut. Laskennallisesti vaikeat ongelmat antavat meille tavan erottaa nämä ryhmät sen perusteella, mitä he tietävät. Mutta jos haluat tietää vastauksen ongelmaan, jotta voit erottaa kaksi ihmisryhmää, et voi käyttää vain mitään vaikeaa ongelmaa – tarvitset kovan palapelin.

Mitä eroa on ongelmalla ja palapelillä?

Yleensä ongelman esittäjä ei välttämättä tiedä vastausta. Palapeli on ongelma, joka on suunniteltu vastaus mielessä. Joten miksi tarvitsemme palapelin? Koska meidän on pystyttävä määrittämään, tekikö henkilö, joka oletettavasti ratkaisi sen, todella. Arjessa käytämme pulmia huvikseen, mutta käytämme niitä myös luokkahuoneissa testataksemme, ymmärsivätkö ihmiset materiaalin. Näin tapahtuu kryptografiassa: Käytämme pulmia testataksemme jonkun tietämystä.

Viiden maailman ero on siinä, kuinka he vastaavat kysymyksiin "Onko vaikeita ongelmia?" ja "Onko vaikeita pulmia?"

Miten nuo erilaiset vastaukset vaikuttavat?

Ensimmäisessä maailmassa, Algorithmicassa, mikään ongelma ei ole vaikea. Sinun ei tarvitse tietää, kuinka joku suunnitteli ongelmasi: voit aina ratkaista sen. Heuristica sanoo: "No, ehkä jotkut ongelmat ovat vaikeita." Sitten pääsemme Pessilandiin, jossa monet ongelmat ovat vaikeita, mutta useimmat pulmat eivät ole. Lähes kaikki ongelmat, joita keksin, jos tiedän ratkaisun, pystyt myös ratkaisemaan sen. Kaikki nämä maailmat ovat huonoja kryptografialle.

Minicryptissä voin luoda pulmia, jotka osaan ratkaista ja jotka ovat sinulle vielä todella haastavia. Ja lopuksi, Cryptomania on maailma, jossa kaksi ihmistä voi seistä julkisella paikalla, jossa salakuuntelija voi kuulla ja yhdessä luoda palapelin, joka on edelleen vaikea salakuuntelijalle.

Mikä sai sinut kirjoittamaan viiden maailman paperin?

Tuolloin tiedettiin, että erilaiset vastaukset P vs. NP -kysymykseen vaikuttaisivat suuresti siihen, millaisia ​​ongelmia voimme ratkaista ja myös millaista turvallisuutta voimme toivoa, mutta laadulliset erot erilaisten helppouden ja helppouden muotojen välillä kovuus ei ollut todella selvää.

Vain muutama vuosi aiemmin julkaistiin erittäin oivaltava paperi, joka esitti erot käyttämällä monia toisiinsa liittyviä kysymyksiä ja noin 20 mahdollista vastausta. Yksi syy siihen, miksi halusin kirjoittaa viiden maailman paperin, oli se, että olimme edistyneet valtavasti näiden muutaman vuoden aikana. Olisi ollut vaikea löytää nimiä 20 mahdolliselle maailmalle.

Joten miksi muotoilla se tällä tavalla, eri maailmoina omituisilla nimillä?

Olin sopinut kirjoittavani tämän artikkelin konferenssia varten. Valvoin myöhään illalla yrittäessäni selvittää, mitä aioin sanoa, ja jossain yhdeltä yöllä eri maailmojen kehystys vaikutti hyvältä idealta. Ja sitten luin sen seuraavana aamuna, ja se vaikutti silti hyvältä idealta – se oli tapa näyttää, kuinka nämä ideat todella vaikuttaisivat maailmaan joutumatta kiinni määrällisiin yksityiskohtiin. Minua on iloisin tässä artikkelissa se, että kuulen monimutkaista tutkimusta tekeviltä ihmisiltä, ​​että tämä oli se artikkeli, joka sai heidät kiinnostumaan alasta perustutkinto-opiskelijoilla.

Ovatko tutkijat sulkeneet pois minkä tahansa viidestä mahdollisesta maailmasta?

Itse asiassa lisäämme lisää – ihmiset ovat alkaneet puhua Obfustopia entistä vahvempien salaustyökalujen maailmana. On hieman masentavaa, että edistyimme niin paljon 1980-luvun lopulla emmekä ole poistaneet yhtään maailmaa sen jälkeen. Mutta toisaalta tiedämme paljon enemmän maailmojen välisistä yhteyksistä ja meillä on a paljon selkeämpi kuva miltä kukin maailma näyttäisi.

Hypoteettisilla maailmoilla on myös toinen rooli monimutkaisuusteoriassa, todisteissa, joissa oletetaan "oraakkelien" olemassaoloa. Joten ensinnäkin mikä on oraakkeli?

Kuvittele, että joku rakentaa nerokkaan laitteen, joka voi ratkaista jonkin ongelman ilman, että tiedämme ongelman ratkaisemiseen käytettävän algoritmin. Sitä oraakkeli on. Jos meillä olisi niin ihmeellinen laite ja laitamme sen tietokoneidemme sisään, se voisi siirtyä rajan laskettavissa olevan ja laskemattoman välillä.

Uskovatko tutkijat, että nämä taikalaatikot voisivat olla olemassa?

Ei, niitä ei todennäköisesti ole olemassa. Oraakkelin tulokset olivat alussa hieman kiistanalaisia, koska ne ovat niin hypoteettisia. Mutta yksi tapa, jolla ne voivat olla hyvin valaisevia, on, kun oraakkelia käytetään mallintamaan ihanteellinen tilanne. Oletetaan, että yrität näyttää, että A ei välttämättä tarkoita B:tä. Aloitat asetuksesta, jossa sinulla on äärimmäisin A, ja osoitat, että se ei vieläkään riitä takaamaan B:tä. Jos pystyt osoittamaan, että vaikka kaikki kertoimet olisivat eduksesi, et silti pysty todistamaan jotain, se on todella vahva todiste siitä, että sen todistaminen tulee olemaan vaikeaa.

Olet myös havainnut yhteyksiä laskennallisen kovuuden ja satunnaisuuden välillä. Miten tuo yhteys toimii?

Se on todella tapa sanoa, että jos et ymmärrä jotain, se saattaa tuntua sattumanvaraiselta. Oletetaan, että ajattelen lukua yhden ja tuhannen välillä. Jos valitsen luvun satunnaisesti, sinulla on yksi tuhannesta mahdollisuus arvata se. Ja jos kysyn – seuraamalla Monty Pythonia – "maileina tunnissa, mikä on eurooppalaisen pääskyn keskimääräinen ilmanopeus?" sinulla on suunnilleen sama mahdollisuus. Se kulkee luultavasti enemmän kuin yksi mailia tunnissa, eikä se todennäköisesti kulje yli tuhat mailia tunnissa.

Tämä ei ole itse asiassa satunnaista - se on deterministisesti vastattava kysymys. Voisimme vain mitata kaikki ympäriinsä lentävät pääskyset, mutta sitä on vaikea määrittää rajallisilla resursseilla, kuten sillä, ettei meillä ole budjettia nielemisnopeuksien mittaamiseen ja että nieleitä ei ole loputtomasti.

Joten oivallus on, että vaikeat ongelmat, joiden ratkaisuja emme tiedä, voivat tarjota "pseudosatunnaisten" numeroiden lähteen, jotka näyttävät satunnaisilta.

Monty Pythonista puheen ollen, tiedän, että olet tehnyt improkomediaa jo pitkään – miten aloitit?

Aloitin apulaisprofessorina San Diegossa vuonna 1991. Ja noin vuoden 94 tienoilla ajattelin: "Minulla ei todellakaan ole paljon elämää osaston ulkopuolella." Joten sain ilmaisen viikkolehden ja selailin klubien ja aktiviteettien luetteloa. Jätin pois kaiken paitsi improkomedian – ajattelin ainakin olevan uskottavaa, että pärjäisin siinä. Tapasin vaimoni tuossa aloittelijaluokassa.

Mitä hän ajatteli?

Hän sanoi, että olin todella kamala. Kun olet loogikko, sinut on koulutettu ajattelemaan aina jokaisen sanan vivahteita. Et halua sanoa mitään väärää. Improvisointi on hienoa siinä mielessä, että se kääntää asian toisin: Tarkoitus ei ole sanoa jotain täydellistä, vaan keksiä jotain nopeasti. Se oli päinvastoin kuin loppuelämäni.

Nykyinen vaimoni piti tauon luokasta, ja kun hän palasi vuotta myöhemmin, onnistuin tekemään häneen vaikutuksen. Se oli 30 vuotta sitten. Käyn edelleen samalla kurssilla saman ohjaajan kanssa.

Onko improvisointi muuttanut tapaasi lähestyä tutkimusta?

Se on hyvä käytäntö olla ylikriittinen jokaisen ajatuksen suhteen. Se on erityisen hyödyllistä yhteistyössä. Kun tein töitä muiden ihmisten kanssa, minulla oli tapana sanoa asioita, kuten: "Mutta tuo idea ei toimi seuraavasta syystä. Se ei ole kirjaimellisesti totta." Improvisoinnissa sinun tulee aina hyväksyä se, mitä kumppanisi sanoo. Ja mielestäni se on hyvä asenne, varsinkin kun teet tutkimusta opiskelijoiden kanssa: Älä hylkää heidän sanomiaan vain siksi, että tiedät sen olevan väärin. On monia hyviä ideoita, jotka eivät ole 100% oikeita.

Kuten mitä?

Kun yrität saada intuitiota ongelmaan, yksi asia, joka auttaa, on aloittaa muutamilla yksinkertaistavilla oletuksilla. Nämä oletukset eivät yleensä pidä paikkaansa, mutta ne voivat auttaa sinua laatimaan tiekartan. Sano: "Jos minulla olisi norsu, voisin päästä vuorten yli. Minulla ei tietenkään ole norsua. Mutta jos tekisin, näin tekisin sen." Ja sitten ymmärrät: "No, ehkä en tarvitse norsua tähän vaiheeseen. Muuli olisi hyvä."

Entä rakkautesi roolipeleihin – onko se vaikuttanut työhösi ollenkaan?

Se ei ehkä vaikuttanut kaikkeen tutkimukseeni, mutta se varmasti vaikutti viiden maailman paperioni. Olen aina ollut yleisesti kiinnostunut fantasiasta ja tieteiskirjallisuudesta ja erilaisten mahdollisten maailmojen keksimisestä – miltä asiat olisivat, jos kaikki olisi toisin?

Miksi roolipelit ovat niin houkutteleva tapa tutkia hypoteettisia maailmoja?

Ihmiset, jotka pitävät spekulatiivisesta fiktiosta, ovat aina keksineet maailmoja. Tolkien on tunnetuin siitä, ja hänellä oli niin massiivinen mielikuvitus, että hänen maailmansa tuntui elävän. Meille, jotka eivät ole niin mielikuvituksellisia, paras tapa saavuttaa se on kutsua ihmisiä ympäristöösi ja pelata. on tapa tehdä se. Nyt se ei ole vain minun maailmani. Se saattoi alkaa niin kuin kuvittelin sen, mutta aivan kuten missä tahansa yhteistyössä, kaikkien muiden panosten ansiosta se on kehittynyt sen ohi.