A kutató, aki új világokat varázsolva kutatja a számításokat | Quanta Magazin

Képzelje el, hogy a számítás természetének megértésére törekszik. Mélyen a vadonban vagy, távol minden ösvénytől, és kifürkészhetetlen üzenetek a körülötted lévő fák törzsébe vannak vésve – BPP, AC⁰[m], Σ₂P, YACC és több száz másik. A karakterjelek próbálnak mondani valamit, de hol kezdjem? Még csak nem is tudod őket egyenesen tartani.

Kevés kutató tett annyit, mint Russell Impagliazzo hogy átvágja ezt a látszólagos káoszt. Impagliazzo 40 éven át a számítási komplexitás-elmélet, a különböző problémák belső nehézségeinek tanulmányozásának élvonalában dolgozik. A leghíresebb nyitott kérdés ezen a területen, az úgynevezett P versus NP probléma, amely azt kérdezi, hogy sok látszólag nehéz számítási probléma valóban könnyű-e – megfelelő algoritmussal. A válasz messzemenő következményekkel járna a tudomány és a modern kriptográfia biztonsága szempontjából.

Az 1980-as és 1990-es években Impagliazzo vezető szerepet játszott a a kriptográfia elméleti alapjai. 1995-ben egy ikonikus dokumentumban fogalmazta meg ezen új fejlemények jelentőségét, amely újrafogalmazta a P versus NP lehetséges megoldásait és néhány kapcsolódó problémát öt hipotetikus világ lakhatnánk, szeszélyesen Algorithmicának, Heuristicának, Pessilandnak, Minicryptnek és Cryptomania-nak nevezett. Impagliazzo öt világa kutatók generációját inspirálta, és továbbra is ők irányítják a kutatást a virágzó alterületen. meta-komplexitás.

És nem csak ezeket a világokat álmodta meg. Impagliazzo az asztali szerepjátékok, például a Dungeons és a Dragons egész életen át tartó rajongója volt, és örömmel találja ki új szabályokat és új felfedezésre váró beállításokat. Ugyanez a játékos szellem élteti improvizatív komédia 30 éves gyakorlatát.

Impagliazzo alapozó munkát is végzett, hogy megvilágítsa a véletlenszerűség alapvető szerepét a számításokban. Az 1970-es évek végén az informatikusok felfedezték, hogy a véletlenszerűség néha előfordulhat algoritmusok javítása az eredendően determinisztikus problémák megoldására – ez az ellentmondásos megállapítás, amely évekig zavarba hozta a kutatókat. Impagliazzo munkája a komplexitáselmélet kutatójával Avi Wigderson és más kutatók az 1990-es években kimutatták, hogy ha bizonyos számítási problémák alapvetően nehezek, akkor az mindig lehetséges véletlenszerűséget használó algoritmusok determinisztikussá alakítására. És fordítva, annak bizonyítása, hogy a véletlenszerűség bármely algoritmusból kiküszöbölhető is bebizonyítaná hogy valóban nehéz problémák vannak.

Quanta beszélt Impagliazzóval a nehéz problémák és a nehéz feladványok közötti különbségről, az orákulumok tanácsadásáról és az improvizációs vígjáték matematikai leckéiről. Az interjút az egyértelműség kedvéért sűrítettük és szerkesztettük.

Mikor kezdett el először érdeklődni a matematika iránt?

Már azelőtt is érdekelt a matematika, hogy valóban tudtam volna, mi az. Harmadik osztályban elkezdtek csúszni a matek jegyeim, mert meg kellett volna tanulnunk a szorzótáblákat, de én nem voltam hajlandó. Anyám azt mondta: „De Russell, te szereted a matematikát, miért nem csinálod ezt?” És azt mondtam: „Ez nem matematika, ez memorizálás. Az igazi matematika nem jár memorizálással.” Ekkor már csak az aritmetikát tanultam, így nem tudom, honnan vettem azt az elképzelést, hogy a matematika elvont fogalmakról szól.

Mi a helyzet az informatikával? A terület egyes részei nagyon elvontak, de a legtöbb ember nem ezekkel találkozik először.

A középiskolában volt egy BASIC programozási tanfolyamom, de nagyon nehéz volt bármit is elvégezni. A programokat papírszalagra kellett áthelyezni, amit ezen a nagyon régi számítógépen kellett végigfuttatni, amely gyakran meghibásodott és kettészakította a papírt. Ezért azt gondoltam, hogy a számítástechnika rettenetesen unalmas.

Logikát akartam tanulni. De sok fogalom, amikor megpróbálta ténylegesen formalizálni őket, számításokat és különösen a számítási korlátokat foglalt magában. Olyan kérdések, mint „Honnan tudhatjuk, hogy a matematikában igazak?” és „Hogyan értjük meg a matematika végzésének nehézségét?” elméleti számítástechnikához, és különösen a komplexitáselmélethez vezetett.

Leghíresebb munkái közül néhány a kriptográfia és a számítási komplexitás elmélete közötti összefüggéseket kutatja. Miért függ össze ez a két terület?

Amikor kriptográfiai rendszert állít fel, különbséget kell tennie a jogos felhasználók között – azok között, akiknek hozzáférést szeretne biztosítani – és mindenki más között. Számításilag nehéz problémák lehetőséget adnak arra, hogy meg tudjuk különböztetni ezeket a csoportokat tudásuk alapján. De ha azt akarja, hogy egy problémára a válasz tudva legyen az ember két csoportjának megkülönböztetésének módja, akkor nem használhat egyetlen nehéz feladatot sem – szükség van egy kemény rejtvényre.

Mi a különbség a probléma és a rejtvény között?

Általában a problémát felvető személy nem tudja a választ. A rejtvény egy olyan probléma, amelyet úgy terveztek, hogy a választ szem előtt tartsák. Akkor miért van szükségünk egy rejtvényre? Mert meg kell tudnunk állapítani, hogy egy személy, aki állítólag megoldotta, valóban megtette-e. A mindennapi életben szórakoztatásra használjuk a rejtvényeket, de a tantermekben is teszteljük, hogy az emberek megértették-e az anyagot. Ez történik a kriptográfiában: Rejtvényekkel teszteljük valaki tudását.

Az öt világ között az a különbség, hogy hogyan válaszolnak a „Vannak nehéz problémák?” kérdésre? és „Vannak kemény rejtvények?”

Hogyan működnek ezek a különböző válaszok?

Az első világban, az Algorithmicában, semmi probléma nem nehéz. Nem kell tudnod, hogyan tervezte meg valaki a problémádat: mindig meg tudod oldani. A Heuristica azt mondja: "Nos, talán néhány probléma nehéz." Aztán eljutunk Pessilandba, ahol sok probléma nehéz, de a legtöbb rejtvény nem. Szinte minden olyan problémát, amit kitalálok, ahol tudom a megoldást, te is meg fogod tudni oldani. Mindezek a világok rosszak a kriptográfia számára.

A Minicryptben olyan rejtvényeket készíthetek, amelyeket tudom, hogyan kell megoldani, és amelyek még mindig komoly kihívást jelentenek számodra. És végül a Cryptomania egy olyan világ, amelyben két ember állhat egy nyilvános helyen, ahol a lehallgató hallhat, és együtt alkothatnak egy rejtvényt, amely még mindig nehéz a lehallgató számára.

Mi motivált arra, hogy megírd az öt világ című dolgozatot?

Akkoriban ismert volt, hogy a P versus NP kérdésre adott eltérő válaszok nagyban befolyásolják, hogy milyen problémákat tudunk megoldani, és azt is, hogy milyen biztonságban reménykedhetünk, de a különböző könnyedségi formák minőségi megkülönböztetése, ill. keménysége nem volt igazán egyértelmű.

Alig néhány évvel korábban volt egy nagyon éleslátó tanulmány, amely a megkülönböztetéseket sok, egymással összefüggő kérdéssel, mintegy 20 válaszlehetőséggel részletezte. Az egyik ok, amiért meg akartam írni az öt világról szóló tanulmányt, az volt, hogy ez alatt a néhány év alatt hatalmas előrelépést tettünk. Nehéz lett volna 20 lehetséges világnak nevet találni.

Miért kell tehát így megfogalmazni, mint különböző világokat, furcsa nevekkel?

Megállapodtam, hogy ezt a tanulmányt egy konferenciára írom. Késő este ébren voltam, és próbáltam kitalálni, mit fogok mondani, és valahol hajnali 1 körül jó ötletnek tűnt a különböző világok keretezése. Aztán másnap reggel elolvastam, és még mindig jó ötletnek tűnt – ez egy módja annak, hogy megmutassam, hogyan hatnak ezek az ötletek a világra anélkül, hogy belemerülnék a mennyiségi részletekbe. Engem az tesz a legjobban ennek a dolgozatnak az örömére, hogy komplex kutatást végző emberektől azt hallom, hogy ez volt az a dolgozat, amely felkeltette az érdeklődésüket a terület iránt egyetemistaként.

A kutatók kizárták az öt lehetséges világ valamelyikét?

Valójában többet adunk hozzá – az emberek elkezdtek beszélni Obfusztópia mint a még erősebb kriptográfiai eszközök világa. Kicsit elszomorító, hogy az 1980-as évek végén ekkora fejlődést értünk el, és azóta egyetlen világot sem iktattunk ki. De másrészt sokkal többet tudunk a világok közötti kapcsolatokról, és van a sokkal tisztább kép hogy az egyes világok hogyan néznek ki.

A hipotetikus világok egy másik szerepet is játszanak a komplexitáselméletben, az „orákulumok” létezését feltételező bizonyításokban. Tehát először is, mi is pontosan az orákulum?

Képzeld el, hogy valaki egy zseniális eszközt épít, amely képes megoldani valamilyen problémát anélkül, hogy ismernénk a probléma megoldására szolgáló algoritmust. Ilyen az orákulum. Ha lenne egy ilyen csodálatos eszközünk, és behelyeznénk a számítógépünkbe, akkor eltolódhatna a határ a kiszámítható és a nem kiszámítható között.

A kutatók szerint ezek a varázsdobozok valóban létezhetnek?

Nem, valószínűleg nem léteznek. Az orákulum eredményei kezdetben némileg ellentmondásosak voltak, mert annyira hipotetikusak. De az egyik módja annak, hogy nagyon tanulságosak legyenek, ha az orákulumot egy ideális helyzet modellezésére használják. Tegyük fel, hogy megpróbálja megmutatni, hogy A nem feltétlenül jelenti B-t. Kezdje azzal a beállítással, ahol a legszélsőségesebb A van, és mutassa meg, hogy ez még mindig nem elegendő a B garantálásához. Ha be tudja mutatni, hogy még akkor is, ha az összes esély az Ön javára még mindig nem tud valamit bizonyítani, ez igazán erős bizonyíték arra, hogy nehéz lesz bizonyítani.

Felfedeztél összefüggéseket a számítási keménység és a véletlenszerűség között is. Hogyan működik ez a kapcsolat?

Valójában ez egy módja annak, hogy ha valamit nem értesz, az véletlenszerűnek tűnhet. Tegyük fel, hogy azt mondom, hogy egy és ezer közötti számra gondolok. Ha véletlenszerűen választom ki a számot, akkor egy az ezerhez az esélye, hogy kitalálja. És ha megkérdezem – a Monty Python nyomán – „mérföld per órában, mekkora egy európai fecske átlagos légsebessége?” nagyjából ugyanannyi esélyed van. Valószínűleg több mint egy mérföldet megy óránként, és valószínűleg nem halad ezer mérföldnél többet.

Ez valójában nem véletlen – ez egy determinisztikusan megválaszolható kérdés. Csak meg tudnánk mérni az összes repkedő fecskét, de nehéz meghatározni korlátozott erőforrásokkal, például ha nincs költségvetésünk a fecskesebesség mérésére, és nincs végtelen számú fecskék.

Tehát a belátás az, hogy olyan nehéz problémák, amelyek megoldását nem ismerjük, véletlenszerűnek tűnő „álvéletlen” számok forrása lehet.

Ha már a Monty Pythonról beszélünk, tudom, hogy már régóta csinálsz improvizatív vígjátékokat – hogyan kezdted?

1991-ben adjunktusként kezdtem San Diegóban. '94 körül pedig azt gondoltam: „Tényleg nem sok életem van a tanszéken kívül.” Így hát megkaptam az ingyenes hetilapot, és átnéztem a klubok és tevékenységek listáját. Az improvizációs vígjátékok kivételével mindent kiiktattam – legalábbis hihetőnek tartottam, hogy rendben leszek vele. A feleségemet abban a kezdő osztályban ismertem meg.

Mit gondolt?

Azt mondja, nagyon szörnyű voltam. Amikor logikus vagy, arra van kiképezve, hogy mindig gondoljon minden szó árnyalatára. Nem akarsz valami helytelent mondani. Az Improv nagyszerű abban, hogy ezt megfordítja: Nem az a lényeg, hogy valami tökéleteset mondjunk, hanem az, hogy gyorsan kitaláljunk valamit. Életem hátralévő részében az ellenkezője volt.

A mostani feleségem szünetet tartott az órán, és amikor egy év múlva visszatért, sikerült lenyűgöznem. Ez 30 éve volt. Még mindig ugyanazt az órát járom, ugyanazzal az oktatóval.

Az improvizáció megváltoztatta a kutatáshoz való hozzáállását?

Jó gyakorlat, hogy ne légy hiperkritikus minden gondolatoddal kapcsolatban. Ez különösen az együttműködéseknél hasznos. Amikor másokkal dolgoztam, ilyeneket szoktam mondani: „De ez az ötlet a következő ok miatt nem fog működni. Ez szó szerint nem igaz.” Az improvizáció során mindig el kell fogadnod, amit a partnered mond. És úgy gondolom, hogy ez egy jó hozzáállás, különösen, ha hallgatókkal kutat: ne utasítson el valamit, amit mondanak, csak azért, mert tudja, hogy az helytelen. Sok jó ötlet van, amelyek nem 100%-ig helyesek.

Mint micsoda?

Amikor megpróbál megérzést szerezni egy problémával kapcsolatban, az egyik dolog, ami segít, az, hogy néhány egyszerűsítő feltevéssel kezdi. Ezek a feltételezések általában nem igazak, de segíthetnek egy ütemterv elkészítésében. Mondd: „Ha lenne elefántom, átjuthatnék a hegyeken. Természetesen nincs elefántom. De ha megtenném, a következőképpen csinálnám.” És akkor rájössz: „Nos, talán nincs szükségem elefántra ehhez a lépéshez. Egy öszvér is jól jönne."

Mi a helyzet a szerepjátékok iránti szeretetével – befolyásolta ez egyáltalán a munkáját?

Lehet, hogy nem volt hatással az összes kutatásomra, de minden bizonnyal hatással volt az öt világról szóló tanulmányomra. Mindig is általánosan érdekelt a fantasy és a sci-fi, és a különböző lehetséges világok kitalálása – milyenek lennének a dolgok, ha minden másképp lenne?

Miért olyan lenyűgöző módja a szerepjáték a hipotetikus világok felfedezésének?

A spekulatív fikciókat kedvelő emberek mindig is világokat találtak fel. Tolkien a leghíresebb róla, és olyan hatalmas fantáziája volt, hogy a világát valóban élve érezte. Nekünk, akik nem vagyunk annyira fantáziadúsak, a legjobb módja annak elérésére, ha meghívunk embereket a környezetünkbe, és egy játékot. egy módja ennek. Most már nem csak az én világom. Lehet, hogy úgy kezdődött, ahogy elképzeltem, de mint minden együttműködésnél, mindenki más közreműködésének köszönhetően ez is jóval túlhaladott.