Predstavljajte si, da iščete razumevanje same narave računanja. Ste globoko v divjini, daleč od vseh poti in nedoumljivo sporočil so vklesani v debla dreves okoli vas — BPP, AC⁰[m], Σ₂P, YACC in na stotine drugih. Glifi vam poskušajo nekaj povedati, toda kje začeti? Sploh jih ne moreš držati naravnost.

Malo raziskovalcev je naredilo toliko Russell Impagliazzo presekati ta navidezni kaos. Impagliazzo je 40 let delal na čelu teorije računalniške kompleksnosti, študije intrinzične težavnosti različnih problemov. Najbolj znano odprto vprašanje na tem področju, imenovano problem P proti NP, sprašuje, ali so številni na videz težki računski problemi dejansko enostavni - s pravim algoritmom. Odgovor bi imel daljnosežne posledice za znanost in varnost sodobne kriptografije.

V 1980. in 1990. letih prejšnjega stoletja je Impagliazzo igral vodilno vlogo pri združevanju teoretične osnove kriptografije. Leta 1995 je ubesedil pomen tega novega razvoja v ikoničnem dokumentu, ki je preoblikoval možne rešitve za P v primerjavi z NP in peščico sorodnih problemov v jeziku pet hipotetičnih svetov bi lahko naselili, muhasto poimenovali Algorithmica, Heuristica, Pessiland, Minicrypt in Cryptomania. Impagliazzovih pet svetov je navdihnilo generacijo raziskovalcev in še naprej usmerja raziskave na cvetočem podpolju metakompleksnost.

In to niso edini svetovi, o katerih je sanjal. Impagliazzo je vse življenje navdušen nad namiznimi igrami vlog, kot je Dungeons and Dragons, in z veseljem izumlja nove sklope pravil in nove nastavitve za raziskovanje. Enak igriv duh animira njegovo 30-letno prakso improvizacijske komedije.

Impagliazzo je opravil tudi temeljno delo pri pojasnjevanju temeljne vloge naključnosti v računanju. V poznih sedemdesetih letih so računalniški znanstveniki odkrili, da lahko naključnost včasih izboljšati algoritme za reševanje inherentno determinističnih problemov - kontraintuitivna ugotovitev, ki je leta begala raziskovalce. Impagliazzovo delo s teoretikom kompleksnosti Avi Wigderson in drugi raziskovalci v devetdesetih letih prejšnjega stoletja so pokazali, da če so nekateri računalniški problemi res v osnovi težki, potem vedno možno za pretvorbo algoritmov, ki uporabljajo naključnost, v deterministične. In obratno, dokazovanje, da je naključnost mogoče izločiti iz katerega koli algoritma bi tudi dokazal da res težki problemi obstajajo.

Quanta se je z Impagliazzom pogovarjal o razliki med težkimi problemi in težkimi ugankami, svetovalnih orakljih in matematičnih lekcijah improvizirane komedije. Intervju je bil zgoščen in urejen zaradi jasnosti.

Kdaj te je prvič začela zanimati matematika?

Matematika me je zanimala, še preden sem zares vedela, kaj je to. V tretjem razredu so mi ocene iz matematike začele padati, ker bi se morali naučiti tabele množenja, pa sem zavrnil. Moja mama je rekla: "Ampak Russell, ti obožuješ matematiko, zakaj ne počneš tega?" In rekel sem: »To ni matematika, to je učenje na pamet. Prava matematika ne vključuje pomnjenja.« Vse, kar sem se takrat naučil, je bila aritmetika, zato ne vem, od kod sem dobil idejo, da gre pri matematiki za abstraktne pojme.

Kaj pa računalništvo? Deli polja so zelo abstraktni, vendar niso tisto, s čimer se večina ljudi najprej sreča.

V srednji šoli sem imel tečaj programiranja BASIC, vendar je bilo res težko kar koli narediti. Programe je bilo treba prenesti na papirnate trakove, ki jih je bilo treba prepeljati skozi ta zelo star računalnik, ki se je pogosto pokvaril in ti papir razpolovil. Zato sem mislil, da je računalništvo strašno dolgočasno.

Nameraval sem študirati logiko. Toda veliko konceptov, ko ste jih poskušali dejansko formalizirati, je vključevalo računanje in zlasti omejitve računanja. Vprašanja, kot je "Kako vemo, da so stvari v matematiki resnične?" in "Kako razumemo težavnost pri matematiki?" pripeljal do teoretičnega računalništva in še posebej teorije kompleksnosti.

Nekaj ​​vaših najbolj znanih del raziskuje povezave med kriptografijo in teorijo računalniške kompleksnosti. Zakaj sta ti dve področji povezani?

Ko postavljate kriptografski sistem, morate razlikovati med zakonitimi uporabniki – ljudmi, ki jim želite omogočiti dostop – in vsemi ostalimi. Računalniško težki problemi nam omogočajo razlikovanje med temi skupinami glede na to, kar vedo. Če pa želite, da je odgovor na problem način za razlikovanje dveh skupin ljudi, ne morete kar tako uporabiti katerega koli težkega problema – potrebujete težko uganko.

Kakšna je razlika med problemom in uganko?

Na splošno oseba, ki postavlja problem, morda ne pozna odgovora. Uganka je problem, zasnovan z mislijo na odgovor. Zakaj torej potrebujemo uganko? Ker moramo biti sposobni ugotoviti, ali je oseba, ki naj bi to rešila, tudi res. V vsakdanjem življenju uporabljamo uganke za zabavo, uporabljamo pa jih tudi v učilnicah, da preverimo, ali ljudje razumejo snov. To se dogaja v kriptografiji: uporabljamo uganke, da preizkusimo znanje nekoga.

Razlika med petimi svetovi je v tem, kako odgovarjajo na vprašanja "Ali obstajajo težki problemi?" in "Ali obstajajo težke uganke?"

Kako se ti različni odgovori odvijajo?

V prvem svetu, Algorithmica, nobena težava ni težka. Ni vam treba vedeti, kako je nekdo zasnoval vaš problem: vedno ga lahko rešite. Heuristica pravi: "No, morda je nekaj težav težkih." Nato pridemo v Pessiland, kjer so številne težave težke, večina ugank pa ne. Skoraj vsako težavo, ki si jo izmislim, če poznam rešitev, jo boste lahko rešili tudi vi. Vsi ti svetovi so slabi za kriptografijo.

V Minicryptu lahko ustvarim uganke, ki jih znam rešiti, a so zate še vedno pravi izziv. In nenazadnje, Cryptomania je svet, v katerem lahko dva človeka stojita na javni lokaciji, kjer prisluškovalec sliši in skupaj sestavita za prisluškovalca še vedno težko uganko.

Kaj vas je motiviralo, da ste napisali knjigo petih svetov?

Takrat je bilo znano, da bi različni odgovori na vprašanje P proti NP močno vplivali na to, kakšne težave lahko rešimo in tudi na kakšno varnost lahko pričakujemo, vendar so kvalitativne razlike med različnimi oblikami enostavnosti in trdota ni bila čisto jasna.

Le nekaj let prej je bil objavljen zelo pronicljiv članek, ki je določil razlike z uporabo številnih medsebojno povezanih vprašanj s približno 20 možnimi odgovori. Eden od razlogov, zakaj sem želel napisati dokument petih svetov, je bil, da smo v teh nekaj letih naredili velik napredek. Težko bi bilo najti imena za 20 možnih svetov.

Zakaj bi torej to uokvirili tako, kot različne svetove s čudnimi imeni?

Strinjal sem se, da bom napisal ta članek za konferenco. Ostajal sem pozno v noč in poskušal ugotoviti, kaj bom povedal, in nekje okoli 1. ure zjutraj se je uokvirjanje različnih svetov zdelo dobra ideja. Naslednje jutro sem jo prebral in še vedno se mi je zdela dobra ideja – bil je način, da pokažem, kako bodo te ideje dejansko vplivale na svet, ne da bi se ujeli v kvantitativne podrobnosti. Pri tem prispevku me najbolj veseli, da od ljudi, ki raziskujejo kompleksnost, slišim, da je bil to prispevek, zaradi katerega so se kot dodiplomski študenti zanimali za to področje.

Ali so raziskovalci izključili katerega od petih možnih svetov?

Pravzaprav dodajamo več – ljudje so začeli govoriti o tem Obfustopia kot svet še močnejših kriptografskih orodij. Malce depresivno je, da smo v poznih osemdesetih naredili tako velik napredek in od takrat nismo odpravili nobenega sveta. A po drugi strani vemo veliko več o povezavah med svetovi in ​​imamo veliko bolj jasno sliko kako bi vsak svet izgledal.

Hipotetični svetovi igrajo tudi drugo vlogo v teoriji kompleksnosti, v dokazih, ki domnevajo obstoj "orakljev". Torej, najprej, kaj točno je orakelj?

Predstavljajte si, da nekdo izdela genialno napravo, ki lahko reši neko težavo, ne da bi mi poznali algoritem za rešitev te težave. To je orakelj. Če bi imeli tako čudežno napravo in bi jo postavili v svoje računalnike, bi se lahko premaknila tam, kjer je meja med tem, kar je izračunljivo in kaj ni.

Ali raziskovalci menijo, da bi te čarobne škatle dejansko lahko obstajale?

Ne, verjetno ne obstajajo. Na začetku so bili rezultati Oraclea nekoliko sporni, ker so tako hipotetični. Toda eden od načinov, kako so lahko zelo razsvetljujoči, je, da se orakelj uporabi za modeliranje idealne situacije. Recimo, da poskušate pokazati, da A ne pomeni nujno B. Začnete z nastavitvijo, kjer imate najbolj skrajno A, in pokažete, da to še vedno ni dovolj za zagotovitev B. Če lahko to pokažete, tudi če so vse možnosti v tvojo korist še vedno nečesa ne moreš dokazati, to je res močan dokaz, ki ga bo težko dokazati.

Odkrili ste tudi povezave med računalniško trdoto in naključnostjo. Kako ta povezava deluje?

To je res način povedati, da če nečesa ne razumete, potem se morda zdi naključno. Recimo, da rečem, da mislim na število med ena in tisoč. Če naključno izberem številko, imate možnost ena proti tisoč, da jo uganete. In če vprašam - po Monty Pythonu - "Kolikšna je povprečna zračna hitrost evropske lastovke v miljah na uro?" imaš približno enako možnost. Verjetno gre več kot eno miljo na uro in verjetno ne več kot tisoč milj na uro.

To pravzaprav ni naključno - to je vprašanje, na katerega je mogoče deterministično odgovoriti. Lahko bi le izmerili vse lastovke, ki letajo naokoli, vendar je to nekako težko določiti z omejenimi viri, na primer, če nimamo proračuna za merjenje hitrosti goltanja in nimamo neskončne zaloge lastovk.

Vpogled je torej, da težki problemi, katerih rešitve ne poznamo, lahko zagotovijo vir "psevdonaključnih" števil, ki so videti naključna.

Ko že govorimo o Monty Pythonu, vem, da se že dolgo ukvarjate z improvizirano komedijo – kako ste začeli?

Začel sem kot asistent profesorja v San Diegu leta 1991. In okoli leta 94 ali tako sem pomislil: "Res nimam veliko življenja zunaj oddelka." Tako sem dobil brezplačen tedenski časopis in pogledal sem seznam klubov in dejavnosti. Izločil sem vse, razen improvizirane komedije - mislil sem, da je vsaj verjetno, da bom v tem OK. Svojo ženo sem spoznal v tistem začetnem razredu.

Kaj si je mislila?

Pravi, da sem bil res grozen. Ko ste logik, ste usposobljeni, da vedno razmišljate o niansi vsake besede. Nočeš reči nekaj napačnega. Improv je odličen v tem, da to obrne: Bistvo ni povedati nekaj popolnega, ampak nekaj hitro izmisliti. Bilo je nasprotje preostalega mojega življenja.

Moja zdajšnja žena si je vzela odmor od pouka in ko se je leto kasneje vrnila, mi je uspelo narediti vtis nanjo. To je bilo pred 30 leti. Še vedno hodim na isti tečaj pri istem inštruktorju.

Ali je izboljšanje spremenilo vaš pristop k raziskovanju?

Dobra praksa je, da niste hiperkritični do vsake svoje misli. To je še posebej koristno pri sodelovanju. Ko sem delal z drugimi ljudmi, sem rekel stvari, kot so: »Toda ta ideja ne bo delovala zaradi naslednjega razloga. To ni dobesedno res.” Pri improvizaciji bi morali vedno sprejeti, kar pravi vaš partner. In mislim, da je to dober odnos, zlasti ko raziskujete s študenti: ne zavrzite nečesa, kar rečejo, samo zato, ker veste, da ni pravilno. Obstaja veliko dobrih idej, ki niso 100% pravilne.

Kot kaj?

Ko poskušate pridobiti intuicijo za težavo, je ena stvar, ki pomaga, ta, da začnete z nekaj poenostavljenimi predpostavkami. Te predpostavke običajno niso resnične, vendar vam lahko pomagajo sestaviti načrt. Recite: »Če bi imel slona, ​​bi lahko preletel gore. Seveda nimam slona. Če pa bi, bi to naredil tukaj.« In potem se zaveš: »No, mogoče za ta korak ne potrebujem slona. Mula bi bila v redu.

Kaj pa vaša ljubezen do iger vlog – je to sploh vplivalo na vaše delo?

Morda ni vplivalo na vse moje raziskave, zagotovo pa je vplivalo na moj članek petih svetov. Vedno sem imel splošno zanimanje za domišljijo in znanstveno fantastiko ter za ustvarjanje različnih možnih svetov – kaj bi bilo, če bi bilo vse drugače?

Zakaj so igre z igranjem vlog tako privlačen način za raziskovanje hipotetičnih svetov?

Ljudje, ki se ukvarjajo s špekulativno fikcijo, so si vedno izmišljali svetove. Tolkien je najbolj znan po tem in imel je tako ogromno domišljijo, da je njegov svet dejansko živel. Za tiste med nami, ki nismo tako domiselni, je najboljši način za to, da povabite ljudi v svoje okolje in igro je način za to. Zdaj to ni samo moj svet. Morda se je začelo tako, kot sem si zamislil, a tako kot pri vsakem sodelovanju se je zaradi prispevkov vseh drugih razvilo daleč čez to.