Cercetătorul care explorează calculul conjurând lumi noi | Revista Quanta

Imaginează-ți că ești într-o încercare de a înțelege însăși natura calculului. Ești adânc în pustie, departe de orice potecă și inscrutabil mesaje sunt sculptate în trunchiurile copacilor din jurul tău — BPP, AC⁰[m], Σ₂P, YACC și sute de alții. Glifele încearcă să vă spună ceva, dar de unde să începeți? Nici măcar nu le poți ține pe toate drepte.

Puțini cercetători au făcut atât de mult Russell Impagliazzo pentru a trece peste acest aparent haos. Timp de 40 de ani, Impagliazzo a lucrat în fruntea teoriei complexității computaționale, studiul dificultății intrinseci a diferitelor probleme. Cea mai faimoasă întrebare deschisă din acest domeniu, numită problema P versus NP, se întreabă dacă multe probleme de calcul aparent dificile sunt de fapt ușoare - cu algoritmul potrivit. Un răspuns ar avea implicații de anvergură pentru știință și securitatea criptografiei moderne.

În anii 1980 și 1990, Impagliazzo a jucat un rol principal în unificarea Fundamentele teoretice ale criptografiei. În 1995, el a articulat semnificația acestor noi dezvoltări într-o lucrare iconică care a reformulat posibile soluții la P versus NP și o mână de probleme conexe în limbajul cinci lumi ipotetice am putea locui, numite capricios Algorithmica, Heuristica, Pessiland, Minicrypt și Cryptomania. Cele cinci lumi ale lui Impagliazzo au inspirat o generație de cercetători și continuă să ghideze cercetarea în subdomeniul înfloritor al meta-complexitatea.

Și acestea nu sunt singurele lumi pe care le-a visat. Impagliazzo a fost un pasionat de o viață de jocuri de rol de masă precum Dungeons and Dragons și îi place să inventeze noi seturi de reguli și noi setări de explorat. Același spirit jucăuș îi animă practica de 30 de ani a comediei de improvizație.

Impagliazzo a făcut, de asemenea, lucrări de bază, elucidând rolul fundamental al aleatoriei în calcul. La sfârșitul anilor 1970, informaticienii au descoperit că aleatorietatea poate uneori îmbunătățirea algoritmilor pentru rezolvarea unor probleme inerent deterministe — o constatare contraintuitivă care i-a perplex pe cercetători ani de zile. Lucrarea lui Impagliazzo cu teoreticianul complexității Avi Wigderson și alți cercetători din anii 1990 au arătat că, dacă anumite probleme de calcul sunt cu adevărat dificile, atunci este întotdeauna posibil pentru a converti algoritmi care folosesc aleatoriu în alții determiniști. Și invers, demonstrând că aleatorietatea poate fi eliminată din orice algoritm ar dovedi de asemenea că există probleme cu adevărat grele.

Cuante a vorbit cu Impagliazzo despre diferența dintre probleme dificile și puzzle-uri dificile, consultarea oracolelor și lecțiile de matematică ale comediei improvizate. Interviul a fost condensat și editat pentru claritate.

Când te-ai interesat prima dată de matematică?

Eram interesat de matematică chiar înainte să știu cu adevărat ce este. În clasa a treia, notele mele la matematică au început să scadă pentru că trebuia să ne memorăm tabelele înmulțirii, iar eu am refuzat. Mama a spus: „Dar Russell, îți place matematica, de ce nu faci asta?” Și i-am spus: „Asta nu este matematică, este memorare. Matematica adevărată nu implică memorare.” Tot ceea ce învățasem în acel moment era aritmetica, așa că nu sunt sigur de unde am luat ideea că matematica era despre concepte abstracte.

Dar informatica? Părți ale domeniului sunt foarte abstracte, dar nu sunt ceea ce majoritatea oamenilor le întâlnesc prima dată.

În liceu, făcusem un curs de programare în BASIC, dar a fost foarte greu să realizez ceva. Programele trebuiau transferate pe benzi de hârtie, care trebuiau să fie rulate prin acest computer foarte vechi care adesea funcționa defectuos și smulgea hârtia în jumătate. Așa că am crezut că informatica este îngrozitor de plictisitoare.

Intenționam să studiez logica. Dar multe dintre concepte, când ai încercat să le oficializezi efectiv, implicau calcul și mai ales limite ale calculului. Întrebări precum „De unde știm că lucrurile din matematică sunt adevărate?” și „Cum înțelegem dificultatea de a face matematică?” a condus la informatica teoretică și în special la teoria complexității.

Unele dintre cele mai faimoase lucrări ale tale explorează conexiunile dintre criptografie și teoria complexității computaționale. De ce sunt legate aceste două domenii?

Când configurați un sistem criptografic, trebuie să faceți distincția între utilizatorii legitimi - persoanele cărora doriți să le acordați acces - și toți ceilalți. Problemele dificile din punct de vedere computațional ne oferă o modalitate de a distinge aceste grupuri pe baza a ceea ce știu. Dar dacă vrei să cunoști răspunsul la o problemă să fie o modalitate de a distinge două grupuri de oameni, nu poți folosi orice problemă dificilă - ai nevoie de un puzzle greu.

Care este diferența dintre o problemă și un puzzle?

În general, persoana care pune o problemă ar putea să nu știe răspunsul. Un puzzle este o problemă concepută cu un răspuns în minte. Deci de ce avem nevoie de un puzzle? Pentru că trebuie să putem determina dacă o persoană care se presupune că a rezolvat-o chiar a făcut-o. În viața de zi cu zi, folosim puzzle-uri pentru distracție, dar le folosim și în sălile de clasă pentru a testa dacă oamenii au înțeles materialul. Iată ce se întâmplă în criptografie: folosim puzzle-uri pentru a testa cunoștințele cuiva.

Diferența dintre cele cinci lumi este modul în care răspund la întrebările „Există probleme grele?” și „Există puzzle-uri grele?”

Cum apar aceste răspunsuri diferite?

În prima lume, Algorithmica, nicio problemă nu este grea. Nu trebuie să știi cum cineva a conceput problema ta: o poți rezolva oricând. Heuristica spune: „Ei bine, poate câteva probleme sunt grele.” Apoi ajungem la Pessiland, unde multe probleme sunt grele, dar majoritatea puzzle-urilor nu. Aproape orice problemă pe care o inventez unde știu soluția, o vei putea rezolva și tu. Toate aceste lumi sunt dăunătoare pentru criptografie.

În Minicrypt, pot crea puzzle-uri pe care știu să le rezolv și care sunt încă foarte provocatoare pentru tine. Și, în cele din urmă, Cryptomania este o lume în care doi oameni pot sta într-o locație publică, unde un interceptător poate auzi și împreună pot crea un puzzle care este încă greu pentru cei care ascultă cu urechea.

Ce te-a motivat să scrii lucrarea celor cinci lumi?

La acea vreme, se știa că răspunsurile diferite la întrebarea P versus NP ar avea un impact mare asupra tipului de probleme pe care le putem rezolva și, de asemenea, la ce fel de securitate putem spera, dar distincțiile calitative dintre diferitele forme de ușurință și duritatea nu erau chiar clare.

Cu doar câțiva ani mai devreme, a existat o lucrare foarte perspicace care a stabilit diferențele folosind multe întrebări interdependente cu aproximativ 20 de răspunsuri posibile. Unul dintre motivele pentru care am vrut să scriu lucrarea celor cinci lumi a fost că am făcut un progres uriaș în acești câțiva ani. Ar fi fost greu să găsești nume pentru 20 de lumi posibile.

Deci, de ce să-l încadreze așa, ca lumi diferite cu nume ciudate?

Am fost de acord să scriu această lucrare pentru o conferință. Stăteam până târziu noaptea încercând să-mi dau seama ce voi spune și undeva în jurul orei 1 dimineața, încadrarea diferitelor lumi mi s-a părut o idee bună. Și apoi l-am citit a doua zi dimineață și încă mi s-a părut o idee OK - era o modalitate de a arăta cum aceste idei ar influența de fapt lumea fără a fi prins în detalii cantitative. Ceea ce mă bucură cel mai mult în legătură cu această lucrare este că aud de la oameni care fac cercetări în complexitate că aceasta a fost lucrarea care i-a făcut să se intereseze de domeniu ca studenți.

Au exclus cercetătorii vreuna dintre cele cinci lumi posibile?

De fapt, adăugăm mai multe - oamenii au început să vorbească despre Obfustopia ca o lume a instrumentelor criptografice și mai puternice. Este puțin deprimant faptul că am făcut atât de multe progrese la sfârșitul anilor 1980 și nu am eliminat nicio lume de atunci. Dar, pe de altă parte, știm mult mai multe despre conexiunile dintre lumi și avem o imagine mult mai clara despre cum ar arăta fiecare lume.

Lumile ipotetice joacă, de asemenea, un alt rol în teoria complexității, în dovezile care presupun existența „oracolelor”. Deci, în primul rând, ce este exact un oracol?

Imaginați-vă că cineva construiește un dispozitiv ingenios care poate rezolva o problemă fără ca noi să cunoaștem un algoritm pentru rezolvarea acelei probleme. Asta este un oracol. Dacă am avea un astfel de dispozitiv miraculos și l-am pune în interiorul computerelor noastre, s-ar putea muta acolo unde este linia dintre ceea ce este computabil și ceea ce nu este computabil.

Cercetătorii cred că aceste cutii magice ar putea exista cu adevărat?

Nu, probabil că nu există. La început, rezultatele oracolului au fost oarecum controversate pentru că sunt atât de ipotetice. Dar o modalitate prin care pot fi foarte iluminatoare este atunci când oracolul este folosit pentru a modela o situație ideală. Să presupunem că încercați să arătați că A nu implică neapărat B. Începeți cu setarea în care aveți cel mai extrem A și arătați că asta încă nu este suficient pentru a garanta B. Dacă puteți demonstra că, chiar dacă toate șansele sunt în favoarea ta încă nu poți dovedi ceva, asta este o dovadă puternică că va fi greu de demonstrat.

De asemenea, ați descoperit legături între duritatea computațională și aleatorie. Cum funcționează acea conexiune?

Este într-adevăr un mod de a spune că, dacă nu înțelegi ceva, atunci ar putea părea întâmplător. Să presupunem că spun că mă gândesc la un număr între unu și o mie. Dacă aleg numărul la întâmplare, ai o șansă de una la o mie de a-l ghici. Și dacă întreb – urmând Monty Python – „În mile pe oră, care este viteza medie a unei rândunice europene?” ai cam aceeasi sansa. Probabil merge mai mult de o milă pe oră și probabil că nu merge mai mult de o mie de mile pe oră.

Aceasta nu este de fapt aleatorie – este o întrebare la care se poate răspunde din punct de vedere determinist. Am putea măsura doar toate rândunelele care zboară în jur, dar este cam greu de determinat cu resurse limitate, cum ar fi să nu ai un buget pentru măsurarea vitezei de rândunele și să nu ai o ofertă infinită de rândunele.

Așadar, ideea este că problemele grele ale căror soluții nu le cunoaștem pot oferi o sursă de numere „pseudoratoare” care par aleatorii.

Apropo de Monty Python, știu că faci comedie de improvizație de multă vreme – cum ai început?

Am început ca profesor asistent în San Diego în 1991. Și în jurul anului ’94 și ceva, m-am gândit: „Nu prea am o viață în afara departamentului.” Așa că am primit ziarul săptămânal gratuit și m-am uitat prin lista de cluburi și activități. Am eliminat totul, cu excepția comediei improvizate – m-am gândit că este cel puțin plauzibil să fiu în regulă. Mi-am cunoscut soția la cursul acela de începători.

Ce a crezut ea?

Ea spune că am fost cu adevărat groaznic. Când ești logician, ești antrenat să te gândești mereu la nuanța fiecărui cuvânt. Nu vrei să spui ceva greșit. Improvizația este grozavă prin faptul că inversează: ideea nu este să spui ceva perfect, ci să inventezi ceva rapid. A fost opusul restului vieții mele.

Soția mea de acum a luat o pauză de la curs, iar când s-a întors un an mai târziu, am reușit să o impresionez. Asta a fost acum 30 de ani. Încă urmez aceeași clasă cu același instructor.

Îmbunătățirea a schimbat modul în care vă abordați cercetarea?

Este o practică bună să nu fii hipercritic cu privire la fiecare gând pe care îl ai. Acest lucru este util în special în colaborări. Când lucram cu alți oameni, obișnuiam să spun lucruri de genul: „Dar această idee nu va funcționa din următorul motiv. Asta nu este adevărat.” În improvizație, ar trebui să accepți întotdeauna ceea ce spune partenerul tău. Și cred că este o atitudine bună de a avea, mai ales când faci cercetări cu studenții: nu respinge ceva ce spun ei doar pentru că știi că este incorect. Există o mulțime de idei bune care nu sunt 100% corecte.

Precum ce?

Când încercați să obțineți intuiție pentru o problemă, un lucru care vă ajută este să începeți cu câteva ipoteze simplificatoare. Aceste presupuneri nu sunt de obicei adevărate, dar vă pot ajuta să găsiți o foaie de parcurs. Spune: „Dacă aș avea un elefant, aș putea trece peste munți. Desigur, nu am un elefant. Dar dacă aș face-o, iată cum aș face-o.” Și apoi îți dai seama: „Ei bine, poate că nu am nevoie de un elefant pentru acest pas. Un catâr ar fi bine.”

Ce zici de dragostea ta pentru jocurile de rol - ți-a influențat asta cumva munca?

Poate că nu mi-a influențat toate cercetările, dar cu siguranță mi-a influențat lucrarea pe cele cinci lumi. Întotdeauna am avut un interes general pentru fantasy și science-fiction și pentru a veni cu diferite lumi posibile - cum ar fi lucrurile dacă totul ar fi diferit?

De ce sunt jocurile de rol o modalitate atât de convingătoare de a explora lumi ipotetice?

Oamenii care sunt în ficțiunea speculativă au inventat întotdeauna lumi. Tolkien este cel mai faimos pentru asta și avea o imaginație atât de uriașă încât lumea lui se simțea trăită de fapt. Pentru aceia dintre noi care nu suntem la fel de imaginativi, cel mai bun mod de a realiza acest lucru este de a invita oamenii în decorul tău și la un joc. este un mod de a face asta. Acum nu este doar lumea mea. Poate că a început așa cum mi l-am imaginat, dar la fel ca în orice colaborare, din cauza contribuțiilor tuturor celorlalți, a evoluat mult peste asta.