Teadlane, kes uurib arvutusi uusi maailmu võludes | Ajakiri Quanta

Kujutage ette, et soovite mõista arvutamise olemust. Sa oled sügaval kõrbes, kaugel igasugustest radadest ja uurimatu kirjad on raiutud teie ümber olevate puude tüvedesse – BPP, AC⁰[m], Σ₂P, YACC ja sajad teised. Glüüfid üritavad sulle midagi öelda, aga millest alustada? Sa ei saa isegi neid kõiki sirgelt hoida.

Vähesed teadlased on teinud nii palju kui Russell Impagliazzo et sellest näilisest kaosest läbi lõigata. Impagliazzo on 40 aastat töötanud arvutusliku keerukuse teooria esirinnas, mis on uurinud erinevate probleemide sisemist raskust. Selle valdkonna kuulsaim avatud küsimus, P versus NP probleem, küsib, kas paljud näiliselt rasked arvutusülesanded on tegelikult lihtsad – õige algoritmiga. Vastusel oleks teadusele ja kaasaegse krüptograafia turvalisusele kaugeleulatuvad tagajärjed.

1980ndatel ja 1990ndatel mängis Impagliazzo juhtivat rolli krüptograafia teoreetilised alused. 1995. aastal sõnastas ta nende uute arengute olulisuse ikoonilises dokumendis, mis sõnastas ümber võimalikud lahendused P versus NP ja käputäis sellega seotud probleeme viis hüpoteetilist maailma me võiksime asustada, veidralt ristitud Algorithmica, Heuristica, Pessiland, Minicrypt ja Cryptomania. Impagliazzo viis maailma on inspireerinud tervet põlvkonda teadlasi ja nad suunavad jätkuvalt uurimistööd õitsvas alamvaldkonnas. meta keerukus.

Ja need pole ainsad maailmad, millest ta unistab. Impagliazzo on olnud eluaegne lauarollimängude, nagu Dungeons ja Dragons, austaja ning talle meeldib leiutada uued reeglid ja uusi seadeid, mida uurida. Sama mänguline vaim elavdab tema 30-aastast improvisatsioonikomöödia praktikat.

Impagliazzo tegi ka alustööd, selgitades juhuslikkuse põhirolli arvutustes. 1970. aastate lõpus avastasid arvutiteadlased, et juhuslikkus võib mõnikord tekkida parandada algoritme olemuselt deterministlike probleemide lahendamiseks – intuitiivne leid, mis tekitas teadlastel aastaid hämmingut. Impagliazzo töö keerukuse teoreetikuga Avi Wigderson ja teised teadlased 1990. aastatel näitasid, et kui teatud arvutusprobleemid on tõesti põhimõtteliselt rasked, siis alati võimalik juhuslikkust kasutavate algoritmide teisendamiseks deterministlikeks. Ja vastupidi, tõestades, et juhuslikkust saab igast algoritmist kõrvaldada tõestaks ka et on tõesti rasked probleemid.

Quanta rääkis Impagliazzoga raskete probleemide ja raskete mõistatuste erinevusest, oraaklite konsulteerimisest ja improkomöödia matemaatikatundidest. Intervjuu on koondatud ja selguse huvides toimetatud.

Millal te esimest korda matemaatika vastu huvi tundsite?

Mind huvitas matemaatika juba enne, kui ma päriselt teadsin, mis see on. Kolmandas klassis hakkasid mu matemaatika hinded libisema, sest me pidime oma korrutustabelid pähe õppima ja ma keeldusin. Mu ema ütles: "Aga Russell, sa armastad matemaatikat, miks sa seda ei tee?" Ja ma ütlesin: "See pole matemaatika, see on päheõppimine. Päris matemaatika ei hõlma päheõppimist. Kõik, mida ma tol hetkel õppisin, oli aritmeetika, nii et ma pole kindel, kust ma sain arusaama, et matemaatika puudutab abstraktseid mõisteid.

Aga arvutiteadus? Valdkonna osad on väga abstraktsed, kuid need ei ole see, millega enamik inimesi esimest korda kokku puutub.

Keskkoolis oli mul programmeerimiskursus BASIC, kuid tegelikult oli raske midagi teha. Programmid tuli üle kanda paberlintidele, mis tuli läbi ajada sellest väga vanast arvutist, mis sageli tõrkes ja rebis su paberi pooleks. Nii et ma arvasin, et arvutiteadus on kohutavalt igav.

Tahtsin loogikat õppida. Kuid paljud mõisted, kui proovisite neid vormistada, hõlmasid arvutamist ja eriti arvutamise piiranguid. Küsimused nagu "Kuidas me teame, et matemaatika asjad on tõesed?" ja "Kuidas me mõistame matemaatika tegemise raskust?" viis teoreetilise arvutiteaduseni ja eriti keerukuse teooriani.

Mõned teie kuulsamad tööd uurivad krüptograafia ja arvutusliku keerukuse teooria vahelisi seoseid. Miks on need kaks valdkonda seotud?

Krüptosüsteemi seadistamisel peate eristama seaduslikke kasutajaid – inimesi, kellele soovite juurdepääsu anda – ja kõiki teisi. Arvutuslikult keerulised probleemid annavad meile võimaluse eristada neid rühmi nende teadmiste põhjal. Kuid kui soovite, et probleemile vastuse teadmine oleks viis kahe inimrühma eristamiseks, ei saa te lihtsalt kasutada rasket ülesannet – vajate rasket mõistatust.

Mis vahe on probleemil ja mõistatusel?

Üldiselt ei pruugi probleemi esitaja vastust teada. Pusle on probleem, mis on loodud vastust silmas pidades. Miks me siis mõistatust vajame? Sest me peame suutma kindlaks teha, kas inimene, kes selle väidetavalt lahendas, seda ka tegelikult tegi. Igapäevaelus kasutame puslesid meelelahutuseks, kuid kasutame neid ka klassiruumides, et kontrollida, kas inimesed said materjalist aru. Krüptograafias juhtub nii: me kasutame mõistatusi, et kontrollida kellegi teadmisi.

Viie maailma erinevus seisneb selles, kuidas nad vastavad küsimustele "Kas on raskeid probleeme?" ja "Kas on raskeid mõistatusi?"

Kuidas need erinevad vastused välja käivad?

Esimeses maailmas, Algorithmicas, pole ükski probleem raske. Te ei pea teadma, kuidas keegi teie probleemi kavandas: saate selle alati lahendada. Heuristica ütleb: "Võib-olla on mõned probleemid rasked." Seejärel jõuame Pessilandi, kus paljud probleemid on rasked, kuid enamik mõistatusi mitte. Peaaegu iga probleemi, mille ma välja mõtlen, kui ma tean lahendust, saate ka selle lahendada. Kõik need maailmad on krüptograafia jaoks halvad.

Minicryptis saan luua mõistatusi, mida ma tean, kuidas lahendada ja mis on teie jaoks endiselt väga rasked. Ja lõpuks, Krüptomaania on maailm, kus kaks inimest saavad seista avalikus kohas, kus pealtkuulaja kuuleb ja koos luua mõistatuse, mis on pealtkuulajale endiselt raske.

Mis ajendas teid viie maailma paberit kirjutama?

Tol ajal oli teada, et erinevad vastused küsimusele P versus NP omavad suurt mõju sellele, milliseid probleeme suudame lahendada ja ka seda, millist turvalisust võime loota, kuid kvalitatiivsed eristused erinevate lihtsuse vormide ja kõvadus ei olnud päris selge.

Vaid paar aastat varem ilmus üks väga põhjalik artikkel, milles esitati eristused, kasutades paljusid omavahel seotud küsimusi ja umbes 20 võimalikku vastust. Üks põhjus, miks ma tahtsin viie maailma paberit kirjutada, oli see, et me olime selle paari aastaga teinud tohutuid edusamme. 20 võimalikule maailmale oleks olnud raske nimesid leida.

Miks siis seda niimoodi kujundada, kui erinevad maailmad ja omapärased nimed?

Olin nõus kirjutama selle ettekande konverentsi jaoks. Olin hilisõhtul üleval, püüdes aru saada, mida ma ütlen, ja kuskil kella 1 paiku öösel tundus erinevate maailmade raamimine hea mõte. Ja siis lugesin seda järgmisel hommikul ja see tundus endiselt hea ideena – see oli viis näidata, kuidas need ideed maailma tegelikult mõjutavad, ilma et oleks kvantitatiivsetesse üksikasjadesse takerdunud. Mind teeb selle töö puhul kõige rohkem rõõmu see, et kuulen keerulisi uuringuid tegevate inimeste käest, et just see paber tekitas neis üliõpilasena selle valdkonna vastu huvi.

Kas teadlased on mõne viiest võimalikust maailmast välistanud?

Me tegelikult lisame rohkem – inimesed on hakanud rääkima Obfustoopia kui veelgi tugevamate krüptograafiliste tööriistade maailm. See on veidi masendav, et tegime 1980. aastate lõpus nii palju edusamme ega ole sellest ajast peale ühtegi maailma kaotanud. Kuid teisest küljest teame palju rohkem maailmadevahelistest seostest ja meil on a palju selgem pilt kuidas iga maailm välja näeks.

Hüpoteetilised maailmad mängivad ka teist rolli keerukuse teoorias, tõendites, mis eeldavad "oraaklite" olemasolu. Niisiis, esiteks, mis täpselt on oraakel?

Kujutage ette, et keegi ehitab geniaalse seadme, mis suudab mõne probleemi lahendada, ilma et me teaksime selle probleemi lahendamise algoritmi. See on oraakel. Kui meil oleks selline imeline seade ja me paneksime selle oma arvutitesse, võib see nihkuda, kus on piir arvutatava ja mittearvutatava vahel.

Kas teadlased arvavad, et need võlukastid võivad tegelikult eksisteerida?

Ei, neid ilmselt ei eksisteeri. Alguses olid oraakli tulemused mõnevõrra vastuolulised, kuna need on nii hüpoteetilised. Kuid üks viis, kuidas need võivad olla väga valgustavad, on see, kui oraaklit kasutatakse ideaalse olukorra modelleerimiseks. Oletame, et üritate näidata, et A ei tähenda tingimata B-d. Alustate seadistusest, kus teil on kõige äärmuslikum A, ja näitate, et sellest ei piisa B garanteerimiseks. Kui suudate näidata, et isegi kui kõik koefitsiendid on teie kasuks ei saa te ikkagi midagi tõestada, see on tõesti tugev tõend, et seda on raske tõestada.

Olete avastanud ka seosed arvutusliku kõvaduse ja juhuslikkuse vahel. Kuidas see ühendus toimib?

See on tõesti viis öelda, et kui te millestki aru ei saa, võib see tunduda juhuslik. Oletame, et ma ütlen, et mõtlen arvule ühe ja tuhande vahel. Kui ma valin numbri juhuslikult, on teil võimalus see ära arvata üks tuhandest. Ja kui ma küsin – järgides Monty Pythonit – „miilides tunnis, mis on euroopa pääsukese keskmine õhukiirus?” teil on umbes sama võimalus. Tõenäoliselt liigub see rohkem kui üks miil tunnis ja tõenäoliselt mitte rohkem kui tuhat miili tunnis.

See pole tegelikult juhuslik – see on deterministlikult vastatav küsimus. Võiksime lihtsalt mõõta kõiki ringi lendavaid pääsukesi, kuid piiratud ressurssidega on seda kuidagi raske kindlaks teha, näiteks kui puudub eelarve neelamiskiiruse mõõtmiseks ja pääsukesi pole lõputult.

Seega on arusaam, et rasked probleemid, mille lahendusi me ei tea, võivad olla juhuslike näivate pseudojuhuslike numbrite allikaks.

Monty Pythonist rääkides, ma tean, et olete improkomöödiat teinud juba pikka aega – kuidas te alustasite?

Alustasin abiprofessorina San Diegos aastal 1991. Ja umbes 94. aasta paiku mõtlesin: "Mul ei ole väljaspool osakonda kuigi palju elu." Nii et sain tasuta nädalalehe ja vaatasin läbi klubide ja tegevuste nimekirja. Kõrvaldasin kõik peale improkomöödia – pidasin vähemalt usutavaks, et saan sellega hakkama. Kohtusin oma naisega selles algklassis.

Mida ta arvas?

Ta ütleb, et ma olin tõesti kohutav. Kui olete loogik, olete treenitud mõtlema alati iga sõna nüansile. Sa ei taha öelda midagi valesti. Improv on suurepärane selle poolest, et see muudab selle ümber: eesmärk ei ole öelda midagi täiuslikku, vaid midagi kiiresti välja mõelda. See oli vastupidine mu ülejäänud elule.

Mu praegune naine tegi tunnist pausi ja kui ta aasta hiljem tagasi tuli, suutsin ma talle muljet avaldada. See oli 30 aastat tagasi. Käin ikka samas klassis sama juhendajaga.

Kas impro tegemine on muutnud seda, kuidas te oma uurimistööle lähenete?

See on hea tava mitte olla iga mõtte suhtes ülikriitiline. See on eriti kasulik koostöös. Teiste inimestega koostööd tehes ütlesin ma näiteks: „Kuid see idee ei tööta järgmisel põhjusel. See pole sõna otseses mõttes tõsi." Improviseerimisel peate alati aktsepteerima seda, mida teie partner ütleb. Ja ma arvan, et see on hea suhtumine, eriti kui teete õpilastega uurimistööd: ärge jätke midagi, mida nad ütlevad, lihtsalt sellepärast, et teate, et see on vale. On palju häid ideid, mis pole 100% õiged.

Nagu mis?

Kui proovite saada intuitsiooni probleemi lahendamiseks, on üks asi, mis aitab alustada mõne lihtsustava eeldusega. Need oletused ei vasta tavaliselt tõele, kuid need võivad aidata teil koostada tegevuskava. Öelge: "Kui mul oleks elevant, saaksin ma üle mägede. Muidugi pole mul elevanti. Aga kui ma seda teeksin, siis teeksin seda järgmiselt. Ja siis mõistad: „Võib-olla pole mul selle sammu jaoks elevanti vaja. Muul sobiks hästi."

Kuidas on lood teie armastusega rollimängude vastu – kas see on teie tööd üldse mõjutanud?

See ei pruugi mõjutada kogu minu uurimistööd, kuid kindlasti mõjutas see minu viie maailma paberit. Mul on alati olnud üldine huvi fantaasia ja ulme vastu ning erinevate võimalike maailmade väljamõtlemine – kuidas oleks, kui kõik oleks teisiti?

Miks on rollimängud nii veenvad viis hüpoteetiliste maailmade uurimiseks?

Spekulatiivse ilukirjandusega tegelevad inimesed on alati maailmu leiutanud. Tolkien on selle poolest kõige kuulsam ja tal oli nii tohutu kujutlusvõime, et tema maailm tundis end tegelikult elavana. Neile meist, kes pole nii fantaasiarikkad, on parim viis selle saavutamiseks kutsuda inimesi oma keskkonda ja mängida. on viis seda teha. Nüüd pole see ainult minu maailm. Võib-olla algas see nii, nagu ma seda ette kujutasin, kuid nagu iga koostöö puhul, on see kõigi teiste panuse tõttu sellest palju möödas.