Zicabange usemkhankasweni wokuqonda yona kanye uhlobo lokubala. Ujulile ehlane, kude nanoma yiziphi izindlela, futhi engafundeki imiyalezo ziqoshwe eziqwini zezihlahla nxazonke zakho — BPP, AC⁰[m], Σ₂P, YACC, namanye amakhulukhulu. Ama-glyphs azama ukukutshela okuthile, kodwa ungaqala kuphi? Awukwazi ngisho ukuwagcina eqondile.

Bambalwa abacwaningi abenze okuningi njengalokhu Russell Impagliazzo ukunqamula lesi siphithiphithi esibonakala sikhona. Iminyaka engu-40, i-Impagliazzo isebenze phambili ku-computational complexity theory, ucwaningo lobunzima obungaphakathi bezinkinga ezahlukene. Umbuzo ovulekile odume kakhulu kulo mkhakha, obizwa ngenkinga ye-P ngokumelene ne-NP, ubuza ukuthi izinkinga eziningi zekhompyutha ezibonakala ziqinile zilula ngempela - nge-algorithm efanele. Impendulo ingaba nemithelela efinyelela kude kwisayensi nasekuvikelekeni kombhalo oyimfihlo wesimanje.

Ngeminyaka yawo-1980 kanye nawo-1990, i-Impagliazzo yabamba iqhaza eliphambili ekuhlanganiseni izisekelo theory of i-cryptography. Ngo-1995, waveza ukubaluleka kwalezi zenzakalo ezintsha ephepheni eliyisakhiwo sodumo elakha kabusha izixazululo ezingaba khona ku-P ngokumelene ne-NP kanye nedlanzana lezinkinga ezihlobene ngolimi imihlaba emihlanu yokucabanga singase sihlale, esibizwa nge-Algorithmica, i-Heuristica, i-Pessiland, i-Minicrypt ne-Cryptomania. Imihlaba emihlanu ye-Impagliazzo ikhuthaze isizukulwane sabacwaningi, futhi bayaqhubeka nokuqondisa ucwaningo endaweni engaphansi echumayo. i-meta-complexity.

Futhi akuwona wodwa umhlaba lawa aphuphile. U-Impagliazzo ube ngumdlali wempilo yonke wemidlalo yokudlala indima ye-tabletop efana ne-Dungeons ne-Dragons, futhi uyakujabulela ukusungula amasethi emisha yemithetho nezilungiselelo ezintsha ongazihlola. Umoya ofanayo wokudlala uvuselela umkhuba wakhe weminyaka engu-30 wamahlaya okuthuthukisa.

I-Impagliazzo iphinde yenza umsebenzi oyisisekelo ecacisa indima ebalulekile yokungahleliwe ekubalweni. Ngasekupheleni kwawo-1970, ososayensi bamakhompiyutha bathola ukuthi ukungahleleki kungase ngezinye izikhathi thuthukisa ama-algorithms ukuze kuxazululwe izinkinga ezinqunyiwe ngokwemvelo - ukutholwa okuphikisayo okwadida abacwaningi iminyaka. Umsebenzi we-Impagliazzo nge-theorist eyinkimbinkimbi Avi Wigderson kanye nabanye abacwaningi ngawo-1990 babonisa ukuthi uma izinkinga ezithile zokubala zinzima ngempela, kusho ukuthi njalo kungenzeka ukuguqula ama-algorithms asebenzisa okungahleliwe abe yi-deterministic. Futhi ngokuphambene, okufakazela ukuthi okungahleliwe kungasuswa kunoma iyiphi i-algorithm izofakazela futhi ukuthi zikhona izinkinga ezinzima ngempela.

I-Quanta ukhulume no-Impagliazzo ngomehluko phakathi kwezinkinga ezinzima namaphazili aqinile, izibikezelo zokubonisana, kanye nezifundo zezibalo zamahlaya angcono kakhulu. Inhlolokhono ifinyeziwe futhi yahlelwa ukuze icaciseleke.

Uqale nini ukuba nentshisekelo kwizibalo?

Nganginesithakazelo ezibalweni nangaphambi kokuba ngazi ngempela ukuthi zaziyini. Ebangeni lesithathu, amamaki ami ezibalo aqala ukushelela ngoba kwakufanele sibambe ngekhanda amatafula ethu okuphindaphinda, ngenqaba. Umama wathi, “Kodwa Russell, uyazithanda izibalo, kungani ungakwenzi lokhu?” Ngase ngithi, “Lezo akuzona izibalo, lokho wukubamba ngekhanda. Izibalo zangempela azihlanganisi ukukhumbula ngekhanda.” Engangikufundile ngaleso sikhathi kwakuyi-arithmetic, ngakho-ke angiqiniseki ukuthi ngiwuthathephi umbono wokuthi izibalo zazimayelana nemiqondo engabonakali.

Kuthiwani ngesayensi yekhompyutha? Izingxenye zenkambu azicacile, kodwa azizona izinto abantu abaningi abaqala ukuhlangana nazo.

Esikoleni samabanga aphezulu, nganginezifundo zokuhlela ku-BASIC, kodwa kwakunzima ngempela ukwenza noma yini. Izinhlelo kwakudingeka zidluliselwe kumakhasethi ephepha, okwakumelwe aqhutshwe kule khompyutha endala eyayivame ukungasebenzi kahle futhi iklebhule iphepha lakho phakathi. Ngakho-ke ngacabanga ukuthi isayensi yekhompiyutha yayilufifi kakhulu.

Ngangihlose ukufunda i-logic. Kepha imiqondo eminingi, ngenkathi uzama ukuyenza ibe semthethweni, yayibandakanya ukubala futhi ikakhulukazi imikhawulo yokubala. Imibuzo efana nokuthi “Sazi kanjani ukuthi izinto zezibalo ziyiqiniso?” kanye nokuthi “Sibuqonda kanjani ubunzima bokwenza izibalo?” kwaholela kusayensi yekhompiyutha yethiyori, kanye nethiyori eyinkimbinkimbi ikakhulukazi.

Omunye wemisebenzi yakho edume kakhulu uhlola ukuxhumana phakathi kwe-cryptography kanye nethiyori eyinkimbinkimbi yekhompyutha. Kungani lezo zindawo ezimbili zihlobene?

Uma usetha isistimu ye-cryptographic, udinga ukuhlukanisa phakathi kwabasebenzisi abasemthethweni - abantu ofuna ukubanikeza ukufinyelela - kanye nawo wonke umuntu. Izinkinga ezinzima ngokwezibalo zisinika indlela yokuhlukanisa la maqembu ngokusekelwe kulokho abakwaziyo. Kodwa uma ufuna ukwazi impendulo yenkinga kube indlela yokuhlukanisa amaqembu amabili abantu, awukwazi ukusebenzisa noma iyiphi inkinga enzima — udinga iphazili eqinile.

Uyini umehluko phakathi kwenkinga nendida?

Ngokuvamile, umuntu obuza inkinga angase angayazi impendulo. Indida inkinga eklanywe ngempendulo engqondweni. Pho kungani sidinga iphazili? Ngoba kudingeka sikwazi ukunquma ukuthi umuntu okuthiwa uyixazulule ngempela yini. Ezimpilweni zansuku zonke, sisebenzisa izindida ukuze sizijabulise, kodwa futhi sizisebenzisa emakilasini ukuze sihlole ukuthi abantu bayakuqonda yini lokho okubalulekile. Yilokhu okwenzeka ku-cryptography: Sisebenzisa izindida ukuze sihlole ulwazi lothile.

Umehluko phakathi kwale mihlaba emihlanu yindlela ephendula ngayo imibuzo ethi “Ingabe zikhona izinkinga ezinzima?” kanye nokuthi “Ingabe akhona amaphazili aqinile?”

Zidlala kanjani lezo zimpendulo ezahlukene?

Ezweni lokuqala, i-Algorithmica, azikho izinkinga ezinzima. Akudingeki wazi ukuthi othile wayiklama kanjani inkinga yakho: Ungahlala uyixazulula. U-Heuristica uthi, "Hhayi-ke, mhlawumbe izinkinga ezimbalwa zinzima." Bese sifika ePessiland, lapho izinkinga eziningi zinzima, kodwa izindida eziningi azikho. Cishe noma iyiphi inkinga engiyenza lapho ngazi khona isixazululo, uzokwazi ukuyixazulula nawe. Yonke le mihlaba ayilungile ekubhalweni kwemfihlo.

Ku-Minicrypt, ngingakwazi ukudala izindida engikwaziyo ukuzixazulula eziseyinselele ngempela kuwe. Ekugcineni, i-Cryptomania iwumhlaba lapho abantu ababili bengama endaweni yomphakathi lapho olalelayo engezwa khona futhi ndawonye bakhe iphazili osekunzima kumuntu olalelayo.

Yini ekugqugquzele ukuthi ubhale iphepha lemihlaba emihlanu?

Ngaleso sikhathi, kwakwaziwa ukuthi izimpendulo ezihlukene zombuzo we-P ngokumelene ne-NP zizoba nomthelela omkhulu ekutheni hlobo luni lwezinkinga esingazixazulula futhi nokuthi hlobo luni lokuphepha esingathembela kukho, kodwa umehluko wekhwalithi phakathi kwezinhlobo ezahlukene zokulula nokulula. ubulukhuni bebungacacile ngempela.

Kube nephepha elinokuqonda eminyakeni embalwa edlule elabeka umehluko kusetshenziswa imibuzo eminingi ehlobene enezimpendulo ezingaba ngu-20. Esinye isizathu esenza ngifune ukubhala iphepha lemihlaba emihlanu ukuthi senze inqubekelaphambili enkulu kuleyo minyaka embalwa. Bekungaba nzima ukuthola amagama emihlaba engama-20 okungenzeka ukuthi ikhona.

Pho kungani ukubeke kanjalo, njengemihlaba ehlukene enamagama angama-quirky?

Ngangivumile ukubhala leli phepha ngengqungquthela. Bengihlala kuze kube sebusuku kakhulu ngizama ukuthola ukuthi ngizothini, futhi ndawana thize ngabo-1 am ukwenza amafreyimu emihlaba ehlukene kwabonakala kuwumqondo omuhle. Ngase ngiyifunda ngakusasa ekuseni futhi kwakubonakala kuwumbono OLUNGILE - kwakuyindlela yokubonisa ukuthi le mibono ingaba nomthelela kanjani emhlabeni ngaphandle kokubanjwa imininingwane yobuningi. Okungijabulisa kakhulu ngaleli phepha wukuthi ngizwa ngabantu abenza ucwaningo oluxakaxaka ukuthi yilona iphepha elabenza bawuthakasela lo mkhakha njengoba bengasafundi.

Ingabe abacwaningi baye banquma ukuthi awukho umhlaba ongaba khona kwemihlanu?

Empeleni sengeza okwengeziwe - abantu sebeqalile ukukhuluma ngakho I-Obfustopia njengomhlaba wamathuluzi e-cryptographic aqine nakakhulu. Kuyadabukisa kancane ukuthi senze inqubekelaphambili enkulu ngasekupheleni kwawo-1980 futhi asikaze sisuse noma yimiphi imihlaba kusukela lapho. Kodwa ngakolunye uhlangothi, sazi okuningi mayelana nokuxhumana phakathi kwemihlaba kanye nokuba ne isithombe esicace kakhudlwana yokuthi umhlaba ngamunye ubungabukeka kanjani.

Imihlaba eqanjiwe nayo idlala enye indima embonweni eyinkimbinkimbi, ebufakazini obucabanga ukuthi kukhona “izibikezelo.” Ngakho, okokuqala, yini ngempela i-oracle?

Cabanga ukuthi othile akha idivayisi ehlakaniphile engaxazulula inkinga ethile ngaphandle kokwazi i-algorithm yokuxazulula leyo nkinga. Yilokho i-oracle eyikho. Uma besinomshini onjalo oyisimangaliso futhi siwufaka ngaphakathi kwamakhompiyutha ethu, ungagudluka lapho umugqa uphakathi kwalokho okusebenzisekayo nalokho okungenakuqhathaniswa.

Ingabe abacwaningi bacabanga ukuthi la mabhokisi omlingo angaba khona ngempela?

Cha, cishe azikho. Ekuqaleni, imiphumela ye-oracle ibiyimpikiswano ngandlela thize ngoba iyacatshangelwa kakhulu. Kodwa enye indlela ezingakhanyisa kakhulu lapho i-oracle isetshenziselwa ukufanisa isimo esihle. Ithi uzama ukukhombisa ukuthi u-A akasho B. Uqala ngesilungiselelo lapho uno-A owedlulele kakhulu futhi ubonise ukuthi lokho akwanele ukuqinisekisa u-B. Uma ungabonisa lokho noma ngabe wonke amathuba ngokuvuna kwakho awukakwazi ukufakazela okuthile, lokho kuwubufakazi obuqinile bokuthi kuzoba nzima ukufakazela.

Uthole nezixhumanisi phakathi kokuqina kwekhompyutha nokungahleliwe. Kusebenza kanjani lokho kuxhumana?

Kuyindlela yokusho ukuthi uma ungaqondi okuthile, kungase kubonakale kungahleliwe. Ake ngithi ngicabanga inombolo phakathi kwenkulungwane eyodwa nenkulungwane. Uma ngikhetha inombolo nomaphi, unethuba elilodwa kweyinkulungwane lokuyiqagela. Futhi uma ngibuza - ngilandela i-Monty Python - "Kumamayela ngehora, ingakanani isivinini somoya senkonjane yaseYurophu?" unethuba elifanayo. Cishe ihamba ngaphezu kwemayela elilodwa ngehora, futhi cishe ayihambi ngaphezu kwamamayela ayinkulungwane ngehora.

Lokhu akukona okungahleliwe - kungumbuzo ophenduleka ngokunquma. Singavele silinganise zonke izinkonjane ezindizayo, kodwa kunzima ukunquma ngezinsizakusebenza ezilinganiselwe, njengokungabi nesabelomali sokulinganisa isivinini sokugwinya kanye nokungabi nokutholakala okungapheli kwenkonjane.

Ngakho-ke ukuqonda ukuthi izinkinga ezinzima izixazululo zazo esingazazi zinganikeza umthombo wezinombolo “zenkohliso” ezibukeka zingahleliwe.

Ngikhuluma ngeMonty Python, ngiyazi ukuthi kudala wenza amahlaya angcono kakhulu - uqale kanjani?

Ngaqala njengomsizi kaprofesa eSan Diego ngo-1991. Futhi cishe ngawo-94 noma ngaphezulu, ngacabanga, “Anginakho ukuphila okuningi ngaphandle komnyango.” Ngakho ngathola iphepha lamahhala lamasonto onke, futhi ngabheka uhlu lwamakilabhu nemisebenzi. Ngisuse yonke into ngaphandle kwamahlaya asezingeni eliphezulu - ngacabanga ukuthi okungenani kunengqondo ukuthi ngizobe ngilungile kukho. Ngahlangana nomkami kulelo klasi labaqalayo.

Wayecabangani?

Uthi ngangimubi ngempela. Uma ungumuntu onengqondo, uqeqeshelwe ukuthi uhlale ucabanga nge-nuance yawo wonke amagama. Awufuni ukusho into engalungile. I-Improv yinhle ngoba ihlehlisa ukuthi: Iphuzu akukhona ukusho into ephelele kodwa ukwenza okuthile ngokushesha. Kwakuphambene nakho konke ukuphila kwami.

Umkami manje wathatha ikhefu ekilasini, futhi lapho ebuya ngemva konyaka, ngakwazi ukumhlaba umxhwele. Lokho kwenzeka eminyakeni engu-30 edlule. Ngisafunda ikilasi elilodwa nomfundisi ofanayo.

Ingabe ukwenza ngcono kuyishintshile indlela owenza ngayo ucwaningo lwakho?

Kuwumkhuba omuhle wokungagxeki ngokweqile ngayo yonke imicabango onayo. Lokho kuyasiza ikakhulukazi ekuhlanganyeleni. Lapho ngenza umsebenzi nabanye abantu, ngangivame ukusho izinto ezinjengokuthi, “Kodwa lowo mbono ngeke usebenze ngenxa yesizathu esilandelayo. Lokho akulona iqiniso ngokwezwi nezwi.” Ngokungcono, kufanele wamukele lokho okushiwo umlingani wakho. Futhi ngicabanga ukuthi leso isimo sengqondo esihle ongaba naso, ikakhulukazi uma wenza ucwaningo nabafundi: Ungachithi into abayishoyo ngoba nje wazi ukuthi ayilungile. Miningi imibono emihle engalungile 100%.

Njengani?

Uma uzama ukuthola intuition yenkinga, into eyodwa ekusizayo ukuqala ngokuqagela okuthile okwenza kube lula. Leyo mibono ngokuvamile ayilona iqiniso, kodwa ingakusiza ukuthi uqhamuke nemephu yomgwaqo. Ithi, “Ukuba benginendlovu, bengingawela izintaba. Impela anginayo indlovu. Kodwa uma ngikwenza, nansi indlela engizoyenza ngayo.” Bese uyaqaphela, “Awu, mhlawumbe angiyidingi ndlovu kulesi sinyathelo. Umnyuzi uzolunga.”

Kuthiwani ngothando lwakho lwemidlalo yokulingisa - ingabe lokho kube nomthelela emsebenzini wakho nakancane?

Kungenzeka ukuthi akuzange kube nomthelela kulo lonke ucwaningo lwami, kodwa ngokuqinisekile kube nomthelela ephepheni lami lemihlaba emihlanu. Bengilokhu nginentshisekelo evamile kunganekwane nesayensi kanye nokuqhamuka nemihlaba ehlukene engaba khona - ngabe izinto beziyoba njani uma yonke into ibihlukile?

Kungani imidlalo yokulingisa iyindlela ephoqelela kangaka yokuhlola imihlaba yokucabanga?

Abantu abagxile ezinganekwaneni eziqagelayo bahlale besungula imihlaba. U-Tolkien waziwa kakhulu ngakho, futhi wayenombono omkhulu kangangokuthi umhlaba wakhe wazizwa ephila kuwo. Kulabo bethu abangebona abacabangayo, indlela engcono kakhulu yokufeza lokho ukumema abantu esilungiselelweni sakho, kanye negeyimu. indlela yokwenza lokho. Manje akuwona nje umhlaba wami. Kungenzeka ukuthi kuqale ngendlela ebengikucabanga ngayo, kodwa njengakunoma yikuphi ukubambisana, ngenxa yeminikelo yawo wonke umuntu kuvele kwadlula lokho.