A komplexitáselmélet 50 éves utazása a tudás határaiig | Quanta Magazin

2007-ben az őszi szemeszter első hetében Marco Carmosino a Massachusetts-i Egyetemen, Amherstben egy matematikaórára húzta magát, amely minden számítástechnika szakon kötelező. A másodéves Carmosino azt fontolgatta, hogy abbahagyja az egyetemet, hogy videojátékokat tervezzen. Aztán a professzor feltett egy egyszerű kérdést, amely megváltoztatja élete menetét: Honnan tudod, hogy a matematika valóban működik?

„Ez arra késztetett, hogy felüljek és figyeljek” – emlékezett vissza Carmosino, jelenleg elméleti informatikus az IBM-nél. Regisztrált egy fakultatív szemináriumra Kurt Gödel munkásságáról, akinek szédítő önreferenciális érvei először tárták fel a matematikai érvelés határait, és megteremtették az alapot a számítások alapvető korlátaival kapcsolatos minden jövőbeni munkához. Sokat kellett belevinni.

„100%-ig nem értettem” – mondta Carmosino. – De tudtam, hogy akarom.

Manapság még a tapasztalt kutatók is hiányosnak találják a megértést, amikor szembesülnek az elméleti számítástechnika központi nyitott kérdésével, amelyet a P versus NP problémának neveznek. Lényegében ez a kérdés azt kérdezi, hogy sok, régóta rendkívül nehéznek tartott számítási probléma valóban könnyen megoldható-e (egy titkos parancsikon keresztül, amelyet még nem fedeztünk fel), vagy, ahogy a legtöbb kutató gyanítja, valóban nehézek-e. A tét nem kevesebb, mint a megismerhető dolgok természete.

Annak ellenére, hogy a kutatók több évtizedes erőfeszítést tettek a számítási komplexitás elmélete terén – a különböző problémák belső nehézségére vonatkozó ilyen kérdések vizsgálata – a P versus NP kérdés megoldása megfoghatatlan maradt. És még az sem világos, hogy hol kezdje a lehetséges bizonyítást.

– Nincs útiterv – mondta Michael Sipser, a Massachusetts Institute of Technology veterán komplexitáselmélete, aki évekig küzdött a problémával az 1980-as években. – Mintha a vadonba mennél.

Úgy tűnik, hogy annak bizonyítása, hogy a számítási problémákat nehéz megoldani, önmagában is nehéz feladat. De miért olyan nehéz? És milyen nehéz? Carmosino és más kutatók a metakomplexitás részterületén újrafogalmazzák az ehhez hasonló kérdéseket, mint számítási problémákat, és a komplexitáselmélet objektívjét önmagára fordítva előremozdítják a területet.

„Azt gondolhatja: „Rendben, ez klassz. Lehet, hogy a komplexitáselméleti szakemberek megőrültek” – mondta Rahul Ilango, az MIT végzős hallgatója, aki a legutóbbi legizgalmasabb eredményeket produkálta ezen a területen.

Ezeknek a befelé forduló kérdéseknek a tanulmányozása során a kutatók rájöttek, hogy a számítási keménység bizonyításának keménysége szorosan összefügg olyan alapvető kérdésekkel, amelyek elsőre úgy tűnhetnek, hogy nincs összefüggésben egymással. Mennyire nehéz észrevenni a rejtett mintákat a látszólag véletlenszerű adatokban? És ha valóban nehéz problémák léteznek, milyen gyakran nehézek?

„Világossá vált, hogy a meta-komplexitás közel áll a dolgok lényegéhez” – mondta Scott aaronson, az austini Texasi Egyetem komplexitáselmélete.

Ez annak a hosszú és kanyargós útnak a története, amely a P versus NP problémától a meta-komplexitásig vezette a kutatókat. Nem volt egyszerű az utazás – az ösvény tele van hamis kanyarokkal és útlezárásokkal, és újra és újra visszakanyarodik önmagába. A meta-komplexitás kutatói számára azonban ez az utazás egy feltérképezetlen tájba a saját jutalma. Kezdj el látszólag egyszerű kérdéseket feltenni mondta Valentine Kabanets, a kanadai Simon Fraser Egyetem komplexitáselmélete, és „fogalma sincs, hová fog menni”.

Ismert Ismeretlenek

A P versus NP probléma halvány elnevezését a komplexitáselméleti szakemberek azon szokásának köszönheti, hogy a számítási problémákat széles kategóriákba rendezik.összetettségi osztályok” a Nasdaq ticker szimbólumokra utaló címkékkel. A számítási probléma elvileg egy algoritmussal – egy pontosan meghatározott utasításlistával – megoldható. De nem minden algoritmus egyformán hasznos, és az algoritmusok közötti eltérések a különböző osztályok problémái közötti alapvető különbségekre utalnak. A komplexitáselméleti szakemberek számára az a kihívás, hogy ezeket a célzásokat szigorú tételekké alakítsák a komplexitási osztályok közötti kapcsolatokról.

Ezek az összefüggések a számításokkal kapcsolatos megváltoztathatatlan igazságokat tükrözik, amelyek messze túlmutatnak minden konkrét technológián. „Ez olyan, mint az univerzum törvényeinek felfedezése” – mondta Kabanets.

„P” és „NP” az a két leghíresebb tagja növekvő menazséria több száz összetettségi osztályból. Nagyjából a P a problémák osztálya, amelyek könnyen megoldhatók, például egy lista ábécé alakítása. Az NP a könnyen ellenőrizhető megoldásokkal, például sudoku rejtvényekkel rendelkező problémák osztálya. Mivel minden könnyen megoldható probléma is könnyen ellenőrizhető, a P-beli problémák NP-ben is megtalálhatók. Néhány NP-probléma azonban nehezen megoldhatónak tűnik – nem lehet azonnal kitalálni a megoldást egy sudoku-rejtvényre anélkül, hogy először kipróbálnánk számos lehetőséget. Lehetséges, hogy ez a látszólagos keménység csak illúzió – hogy egyetlen egyszerű trükk van minden könnyen ellenőrizhető probléma megoldására?

Ha igen, akkor P = NP: A két osztály egyenértékű. Ha ez a helyzet, akkor léteznie kell valamilyen algoritmusnak, amely triviálissá teszi a hatalmas sudoku-rejtvények megoldását, a globális szállítási útvonalak optimalizálását, a legmodernebb titkosítás feltörését és a matematikai tételek bizonyításának automatizálását. Ha P ≠ NP, akkor sok elvileg megoldható számítási probléma a gyakorlatban örökre megfoghatatlan marad.

A kutatók már jóval azelőtt aggódtak a formális matematikai érvelés korlátai miatt, hogy a P versus NP problémát először megfogalmazták volna – sőt, jóval a modern számítástechnika kezdete előtt. 1921-ben, ugyanazzal a kérdéssel küszködve, amely csaknem egy évszázaddal később felkeltette Carmosino figyelmét, David Hilbert matematikus kutatási programot javasolt a matematika teljes bizonyossággal megalapozására. Remélte, hogy néhány egyszerű feltevésből, úgynevezett axiómából indul ki, és egy egységes matematikai elméletet vezet le, amely három kulcskritériumnak felel meg.

Hilbert első feltétele, a konzisztencia volt az a lényeges követelmény, hogy a matematika ellentmondásmentes legyen: Ha két egymásnak ellentmondó állítást ugyanazon axiómákból kiindulva be lehetne bizonyítani, akkor az egész elmélet menthetetlen lenne. De egy elmélet lehet ellentmondásmentes, és még mindig korlátozott. Ez volt a motivációja Hilbert második feltételének, a teljességnek: az a követelmény, hogy minden matematikai állítás vagy bizonyíthatóan igaz, vagy bizonyíthatóan hamis legyen. Harmadik kritériuma, az eldönthetőség, egyértelmű mechanikus eljárást követelt meg annak meghatározására, hogy bármely matematikai állítás igaz-e vagy hamis. Egy 1930-as konferencián Hilbert kijelentette: „Szlogenünk a következő lesz: „Tudnunk kell, tudni fogjuk”.

Alig egy évvel később Gödel megadta az első csapást Hilbert álmára. Ő bizonyított hogy az „ez az állítás bizonyíthatatlan”-hoz hasonló önpusztító állítás az axióma bármely megfelelő halmazából származtatható. Ha egy ilyen állítás valóban bizonyíthatatlan, akkor az elmélet hiányos, de ha bizonyítható, akkor az elmélet következetlen – ez még rosszabb eredmény. Ugyanebben a dolgozatban Gödel azt is bebizonyította, hogy egyetlen matematikai elmélet sem tudja bizonyítani saját következetességét.

A kutatók továbbra is reménykedtek abban, hogy a matematika jövőbeli elmélete, bár szükségszerűen hiányos, mégis eldönthetőnek bizonyulhat. Talán olyan eljárásokat dolgozhatnának ki, amelyek azonosítják az összes bizonyítható állítást, miközben elkerülik az olyan bosszantó kijelentéseket, mint Gödel. A baj az volt, hogy senki sem tudta, hogyan érveljen ezekről a hipotetikus eljárásokról.

Aztán 1936-ban egy 23 éves végzős diák, Alan Turing újrafogalmazta Hilbert eldönthetőségét a számítás akkor még nem ismert nyelvén, és végzetes csapást mért rá. Turing matematikai modellt fogalmazott meg – ma a Turing gép — amely az összes lehetséges algoritmust reprezentálná, és megmutatta, hogy ha Hilbert eljárása létezne, az beleférne ebbe a modellbe. Ezután olyan önreferenciális módszereket alkalmazott, mint Gödel bizonyítani eldönthetetlen állítások létezése – vagy ezzel egyenértékű, kiszámíthatatlan problémák, amelyeket egyetlen algoritmus sem tudna megoldani.

Hilbert programja romokban hevert: Örökre alapvető korlátai lesznek annak, hogy mit lehet bizonyítani és mit lehet kiszámítani. De ahogy a számítógépek elméleti absztrakcióiból valódi gépekké fejlődtek, a kutatók rájöttek, hogy Turing egyszerű megkülönböztetése megoldható és megoldhatatlan problémák között sok kérdést megválaszolatlanul hagyott.

Az 1960-as évekre az informatikusok gyors algoritmusokat fejlesztettek ki bizonyos problémák megoldására, míg mások számára az egyedüli ismert algoritmusok kínosan lassúak voltak. Mi van akkor, ha nem csak az a kérdés, hogy megoldhatók-e a problémák, hanem az, hogy mennyire nehéz őket megoldani?

„Egy gazdag elmélet jelenik meg, és már nem tudjuk a válaszokat” – mondta Carmosino.

Különböző utak

Annak szemléltetésére, hogy mennyire zavarba ejtőek lehetnek a keménységgel kapcsolatos kérdések, nézzünk meg egy pár, egymással szorosan összefüggő problémát, amelyek grafikonokat foglalnak magukban. Ezek pontok hálózatai, úgynevezett csomópontok, amelyeket vonalak kötnek össze, amelyeket éleknek neveznek. Az informatikusok ezek segítségével mindent modelleznek kvantumszámítás hoz a forgalom áramlását.

Tegyük fel, hogy kap egy gráfot, és arra kéri, hogy találjon valamit, amit Hamiltoni útvonalnak neveznek – egy olyan útvonalat, amely minden csomóponton pontosan egyszer halad át. Ez a probléma elvileg egyértelműen megoldható: csak véges számú lehetséges út létezik, így ha minden más nem sikerül, egyszerűen ellenőrizheti mindegyiket. Ez rendben van, ha csak néhány csomópont van, de még egy kicsit nagyobb grafikonokon is a lehetőségek száma kicsúszik az irányítás alól, és gyorsan használhatatlanná teszi ezt az egyszerű algoritmust.

Vannak kifinomultabb Hamilton-útvonal-algoritmusok, amelyek jobban felvették a harcot, de az algoritmusok által a probléma megoldásához szükséges idő mindig exponenciálisan növekszik a gráf méretével. A grafikonoknak nem kell túl nagyoknak lenniük, mielőtt még a legjobb algoritmuskutatók is rájöttek, hogy „ésszerű időn belül” nem találnak utat. Russell Impagliazzo, a San Diego-i Kaliforniai Egyetem komplexitáselmélete. "És az "ésszerű idő" alatt azt értem, hogy "az univerzum véget ér".

A Hamilton-útprobléma egy másik érdekes tulajdonsággal is rendelkezik. Ha valaki azt állítja, hogy talált egy Hamilton-görbe egy adott gráfon, akkor gyorsan ellenőrizheti, hogy a megoldás érvényes-e, még akkor is, ha a gráf nagyon nagy. Mindössze annyit kell tennie, hogy kövesse az útvonalat, és egyenként kipipálja a csomópontokat, és ellenőrizze, hogy nem jelölte-e ki kétszer egyik csomópontot sem. Ha egyetlen csomópont sem hiányzik a végén, akkor az útvonal Hamilton-féle.

A megoldás-ellenőrző algoritmus futtatásához szükséges idő arányos a gráf méretével. Ez a polinomiális algoritmusok tágabb kategóriájába sorolja, amelyek futásideje a gráf méretének polinomiális függvényeivel nő. A polinomiális növekedés szelíd az exponenciális növekedéshez képest, így a polinomiális algoritmusok még nagy grafikonokon is életképesek maradnak. „Ez drámaian hatékonyabb” – mondta Carmosino.

A Hamilton-útprobléma éles aszimmetriával rendelkezik: a helyes megoldást gyors polinomiális algoritmussal ellenőrizheti, de a megoldás megtalálásához lassú exponenciális algoritmusra lesz szüksége. Ez az aszimmetria talán nem tűnik meglepőnek – könnyebb felismerni egy művészi remekművet, mint létrehozni, egyszerűbb a matematikai bizonyítást ellenőrizni, mint egy új tételt bizonyítani –, mégsem minden számítási probléma rendelkezik ezzel az aszimmetrikus jelleggel. Valójában a Hamiltoni utak megtalálásához nagyon hasonló probléma egészen másként viselkedik.

Tegyük fel, hogy ismét kap egy gráfot, de most meg kell találnia egy „Euleri-pályát”, amely minden élt pontosan egyszer keresztez. Ismét van egy polinomiális algoritmus a lehetséges megoldások ellenőrzésére, de ezúttal is van egy polinomiális algoritmus a probléma megoldására. Itt nincs aszimmetria. A komplexitáselméletben egyes utak könnyebben megtalálhatók, mint mások.

Mind a Hamilton-útprobléma, mind az Euleri-útprobléma az NP komplexitási osztályba tartozik, amely úgy van meghatározva, hogy magában foglalja az összes olyan problémát, amelyek megoldása polinomiális algoritmusokkal ellenőrizhető. Az Euleri-útprobléma is a P osztályba tartozik, mert egy polinomiális algoritmus meg tudja oldani, de ez minden jel szerint nem igaz a Hamilton-pálya feladatra. Miért különbözne ennyire drámaian ez a két, felületesen hasonló gráfprobléma? Ez a P versus NP probléma lényege.

Univerzálisan kemény

Eleinte a komplexitási osztályok kényelmes kategóriáknak tűntek a hasonló, de nem közvetlenül összefüggő problémák rendezéséhez – senki sem gyanította, hogy a Hamilton-pályák megtalálásának köze van más nehéz számítási problémákhoz.

Aztán 1971-ben, egy éven belül a Torontói Egyetemre költözött, miután megtagadták tőle a hivatali jogviszonyt az Egyesült Államokban, a komplexitáselmélet kutatója Stephen Cook közzétett egy rendkívüli eredmény. Egy különös NP-problémát egy furcsa tulajdonsággal azonosított: Ha van egy polinomiális algoritmus, amely meg tudja oldani ezt a problémát, akkor az NP minden más problémáját is meg tudja oldani. Cook „univerzális” problémája, úgy tűnt, egy magányos oszlop volt, amely a látszólag nehéz problémák osztályát támasztotta alá, és elválasztja őket az alábbi könnyű problémáktól. Oldja fel ezt az egy problémát, és az NP többi része összeomlik.

Cook gyanította, hogy nincs gyors algoritmus az univerzális problémájára, és ezt mondta a lap közepén, hozzátéve: „Úgy érzem, megéri jelentős erőfeszítéseket fektetni ennek a sejtésnek a bizonyítására.” A „jelentős erőfeszítés” alábecsülésnek bizonyulna.

Ugyanebben az időben egy végzős diák a Szovjetunióban nevezett Leonyid Levin bebizonyosodott a hasonló eredmény, kivéve, hogy több különböző univerzális problémát azonosított. Ráadásul az amerikai komplexitáselméleti szakember Richard Karp bizonyított hogy a Cook (és Levin, bár Karp és Cook csak évekkel később tudott Levin munkásságáról) által azonosított univerzalitási tulajdonság maga is teljesen univerzális. Szinte minden ismert polinomiális algoritmus nélküli NP-probléma – azaz szinte minden könnyen ellenőrizhető, nehéznek tűnő probléma – ugyanazzal a tulajdonsággal rendelkezett, amely NP-teljesség néven vált ismertté.

Ez az összes NP-teljes problémát jelenti – a Hamilton-útprobléma, a sudoku és ezer másoktól – pontos értelemben egyenértékűek. „Mindegyik különböző természetes feladatai vannak, és varázsütésre kiderül, hogy ugyanaz a feladat” – mondta Ilango. "És még mindig nem tudjuk, hogy ugyanaz a feladat lehetséges-e vagy sem."

Bármely NP-teljes probléma nehézségének megoldása elegendő lenne a P versus NP kérdés megoldásához. Ha P ≠ NP, akkor a könnyű és nehéz problémák közötti különbséget több ezer oszlop tartja fenn, amelyek mindegyike egyformán erős. Ha P = NP, akkor az egész építmény az összeomlás szélén billeg, és csak arra vár, hogy egyetlen darab leessen.

Cook, Levin és Karp egyesítette a látszólag sok független problémát. Most a komplexitáselméleti szakembereknek csak egy problémát kellett megoldaniuk: P = NP vagy sem?

Ötven évvel később a kérdés megválaszolatlan marad. Kabanets a számítások korlátairól való okoskodást egy hatalmas terület felméréséhez hasonlította, anélkül, hogy az összképet megértené. Egy korlátlan számítási erejű lény lenézhet a hegytetőről, és egyszerre behatja az egész tájat, de egyszerű halandók nem számíthatnak ilyen előnyre. „Azok, akik a hegy alján vagyunk, megpróbálhatunk fel-le ugrálni, hogy jobban láthassák” – mondta.

Tegyük fel, hogy P = NP. Ennek bizonyításához a kutatóknak gyors algoritmust kell találniuk egy NP-teljes probléma megoldására, amely a hatalmas táj valamely homályos szegletében rejtőzhet. Nincs garancia arra, hogy egyhamar megtalálják: a komplexitás-elméleti szakemberek időnként megtették felfedezett zseniális algoritmusok látszólag nehéz (bár nem NP-teljes) problémákra csak évtizedes munka után.

Most tegyük fel, hogy P ≠ NP. Ezt bizonyítani még nehezebbnek tűnik. A komplexitáselméleti szakembereknek meg kellene állapítaniuk, hogy nem létezhet olyan gyors algoritmus, amely hatékonyan megelőlegezi és meghiúsítja a jövőbeli kutatók legjobb erőfeszítéseit.

A probléma része, hogy nem tudja, hol kezdjem. De nem mintha a kutatók nem próbálkoztak volna. Az évtizedek során sok oldalról támadták a problémát, és minden fordulatnál elzárva találták az utat. „Ez az egyik legkirívóbb igazság az elméleti számítástechnikában” – mondta Carmosino. "Ha van egy olyan jelenség, amely ennyire tartós, magyarázatot szeretne."

Carmosinót a főiskola utolsó évében a kíváncsisága elvezette Gödeltől egy posztgraduális komplexitáselméletre. Meglepődve vette észre, hogy több időt tölt házi feladattal, mint szenvedélyprojektjével, egy számítógépes programmal, amely megtanulja a mesék narratív szerkezetét, és újakat generál.

„Azt gondoltam: „Hú, ezt komolyan kell vennem” – emlékezett vissza Carmosino. Nemsokára annyira elmerült a témában, hogy mentora gyengéden javasolta, gondolja át az érettségi utáni terveit.

„Azt mondta: „Tudod, ha folytatni akarod ezt, ha folytatni akarod az elméleti számítástechnikát és a komplexitáselméletet, megteheted: ezt egyetemi iskolának hívják” – mondta Carmosino. Miután megszerezte a mesterdiplomát, 2012-ben San Diegóba költözött, hogy Impagliazzo által felügyelt doktori címen dolgozzon.

Carmosino fő célja először az volt, hogy jobban megértse a mérföldkő papír két évtizeddel korábban, ami megragadta a képzeletét. Az a papír, a komplexitáselméleti szakemberektől Alekszandr Razborov és a Steven Rudich, megmutatta, hogy egy bizonyos „természetes” stratégia a P ≠ NP bizonyítására szinte biztosan kudarcot vall, mert a siker meredek ára – a kriptográfia teljes összeomlása – járna, amit a kutatók nagyon valószínűtlennek tartottak. A kutatók Razborov és Rudich eredményét a P ≠ NP bizonyítására irányuló népszerű megközelítés gátjaként értelmezték.

Ez a „természetes bizonyítási akadály” csak egy a sok ismert akadály közül a komplexitáselméleti nyitott problémák megoldásában. Mindegyik útlezárásként működik, figyelmeztetve, hogy egy ígéretesnek tűnő út valójában zsákutca. Ezek a korlátok együttesen azt jelzik, hogy minden olyan bizonyítéknak, amely megoldja a P versus NP problémát, radikálisan másnak kell lennie, mint bármi, amit a múltban használtak; ezért a legtöbb kutató úgy véli, hogy a megoldás messze van. De legalább a korlátok megmondják nekik, hová ne nézzenek.

„A komplexitáselmélet egyszerre átkozott és megáldott annyi korláttal” – mondta Ilango.

Mire Carmosino találkozott a természetes bizonyítási korláttal, már majdnem 20 éves volt. De gyanította, hogy ez több tanulsággal szolgál a kutatók számára. Ez az érzés egy napon beigazolódna, amikor három kollégájával meglepő eredményre jutott a természetes bizonyítási korlátot a meta-komplexitás szemszögéből vizsgálva. Bizonyítékuk egyike volt azon néhány jelentős eredménynek, amelyek új érdeklődést váltottak ki a meta-komplexitás iránt, ami az elmúlt néhány évben hatalmas előrelépéshez vezetett.

De ahhoz, hogy a természetes bizonyítási korláttól a meta-komplexitásig kövessük a nyomot, vissza kell ugranunk oda, ahol a kutatókat az 1970-es években hagytuk, amikor először foglalkoztak a P versus NP problémával. Mitől volt olyan nehéz bizonyítani a problémákat?

Egy körkörös ösvény

Eleinte a kutatók megpróbálták bebizonyítani, hogy P ≠ NP – vagyis, hogy egyes NP-problémák nem oldhatók meg semmilyen lehetséges polinomiális algoritmussal – a Turing által használt technikák variációival, hogy bebizonyítsák, hogy bizonyos problémák semmilyen algoritmussal nem oldhatók meg. . De gyorsan felfedezett bizonyíték arra, hogy ezek a módszerek nem működnek – ez az első jelentős akadály a P versus NP kérdés megoldásában. Így hát elkezdtek más megközelítést keresni, és hamarosan találtak is egyet Turing kortársának munkáiban claude shannon.

Shannon, aki egy észak-michigani kisvárosban nőtt fel, valószínűtlen figurának tűnt az információs korszak beindításában. Mégis jól példázta a számítástechnika feltörekvő tudományágának interdiszciplináris jellegét, egyformán otthon érezte magát az elektrotechnikában és a matematikai logikában. Az övében mesterdolgozatShannon bemutatta, hogy az elektromechanikus kapcsolókból készült áramkörök hogyan reprezentálhatnak logikai kifejezéseket Boole-változókkal – olyan mennyiségekkel, amelyek csak két értéket vehetnek fel (például igaz vagy hamis, vagy 1 és 0).

Ezekben a kifejezésekben a logikai változókat az AND, OR és NOT „logikai kapuk” kapcsolják össze. Az A ÉS B elemi kifejezés például igaz, ha A és B is igaz, egyébként pedig hamis; A VAGY B viszont akkor igaz, ha a két változó közül legalább az egyik igaz. A NOT kapu még egyszerűbb: egyetlen változó értékét megfordítja. Ha elegendő ezekből az alapvető építőelemekből, bármilyen számítást elvégezhet.

„Ha ránéz a számítógépére, a nap végén mit csinál az? Egy kört fut” – mondta Ilango.

Shannon munkája egy új módszert javasolt a teoretikusok számára a számítási problémák nehézségeiről, az úgynevezett „áramköri bonyolultságról”, noha a kérdéses áramkörök csak matematikai absztrakciók. Egy ideig a kutatók úgy gondolták, hogy ez a megközelítés lehet a P és az NP feloldásának módja, de végül a nyom a természetes bizonyítási korlátnak ütközött.

Az áramkör bonyolultsági keretrendszere megköveteli a Turing-féle számítási modell legalapvetőbb fogalmainak újragondolását. Itt a számítási problémák és az azokat megoldó algoritmusok helyett a Boole-függvényeket és az azokat kiszámoló áramköröket veszik figyelembe a kutatók. Egy logikai függvény logikai változókat vesz fel – igaz és hamis, 1-es és 0-s értékeket –, és igaz vagy hamis értéket ad ki, 1-et vagy 0-t. És az algoritmusokhoz hasonlóan az áramkör is leír egy eljárást, amellyel bármilyen bemenet mellett kimenetet állíthatunk elő.

„Úgy értem, hogy az emberek azért kezdtek el az áramkörök bonyolultságán dolgozni, mert úgy döntöttek, hogy a Turing-gépek túl bonyolultak” – mondta Ryan Williams, az MIT komplexitáselmélete. – Kapuról kapura tanulmányozhatjuk az áramköröket.

Ahogyan sok algoritmus létezik egy adott számítási probléma megoldására, némelyik gyorsabb, mint mások, sok különböző áramkör képes bármilyen Boole-függvényt kiszámítani, némelyikük kevesebb kapuval, mint mások. A kutatók egy függvény áramkör-bonyolultságát úgy határozzák meg, mint az azt kiszámoló legkisebb áramkör kapuinak teljes számát. Egy fix számú bemeneti változóval rendelkező függvénynél az áramkör bonyolultsága is fix szám – egyes függvényeknél magasabb, mint másoknál.

De sok esetben ugyanannak a függvénynek a bonyolultabb változatait is figyelembe veheti a bemeneti változók számának növelésével, ahogy a Hamilton-pálya problémáját is megnehezítheti nagyobb gráfok figyelembevételével. A kutatók ezután ugyanazt a kérdést vetik fel, amikor az algoritmus futási idejét vizsgálják: A logikai függvény kiszámításához szükséges kapuk minimális száma polinomiálisan vagy exponenciálisan nő a bemeneti változók számának növekedésével? A kutatók ezt a két függvénykategóriát „könnyen kiszámíthatónak”, illetve „nehezen kiszámíthatónak” nevezik.

Egy könnyen kiszámítható Boole-függvény hasonló a P osztályba tartozó számítási problémához – amely egy polinomiális időben futó algoritmussal oldható meg. De vannak olyan függvények is, amelyek a kemény NP-problémákkal analógok, ahol a kutatók által felfedezett legjobb módszer a fokozatosan nagyobb verziók kiszámítására exponenciálisan növekvő számú kaput igényel, de a válasz könnyen ellenőrizhető. Ha a komplexitáselméleti szakemberek be tudnák bizonyítani, hogy valóban nincs jobb módszer egy ilyen függvény kiszámítására, az azt jelentené, hogy P ≠ NP.

Ez volt az a stratégia, amelyet a legtöbb komplexitáselmélet képviselője követett az 1980-as években. És az esélyek az ő oldalukon voltak. Shannonnak volt bizonyított 1949-ben, hogy szinte minden Boole-féle igazságtáblázat (amely csak egy hosszú lista a rögzített méretű Boole-függvény összes lehetséges bemenetéről és kimenetéről) gyakorlatilag a lehető legmagasabb áramkör bonyolultságú. Megdöbbentően egyszerű érvelést alkalmazott: Sokkal kevesebb módja van kis számú kapu kombinálásának, mint sok kapu kombinálásának.

"Egyszerűen nincs elég kis körút a körbejáráshoz" - mondta Aaronson.

A komplexitáselméleti szakemberek tehát különös helyzetbe kerültek. Ha szinte minden igazságtáblázat magas áramköri bonyolultságú, akkor szinte minden Boole-függvényt nehéz kiszámítani. A kutatóknak csak egyetlen ilyen funkciót kellett azonosítaniuk, amelyről ismert volt, hogy az NP osztályba tartozik. Milyen nehéz lehet?

Crypto Bros

Eleinte gyors volt a fejlődés. 1981-ben Sipser és két munkatársa bizonyított hogy egy bizonyos Boole-függvényt határozottan nehéz volt kiszámítani, ha olyan áramköröket használtak, amelyek bizonyos korlátozásokkal rendelkeznek a kapuk elrendezésére vonatkozóan.

„Az volt a képzelet, hogy képes lesz bizonyítani dolgokat ezekkel a korlátozott modellekkel kapcsolatban, majd a megtanultakra építhet, hogy egyre kevesebb megszorítással működjön” – mondta Sipser.

1985-ben Razborov megtette a következő nagy lépést. Éppen most kezdte a posztgraduális iskolát Moszkvában, és véletlenül csatlakozott az erőfeszítéshez, miközben a matematika egy másik ágában egy problémát kezelt, ahol kiderült, hogy a P versus NP probléma megoldása előfeltétel.

„Egyszerűen szerencsés voltam, mert nem tudtam, milyen nehéz ez a probléma” – mondta Razborov. – Különben talán el sem kezdtem volna.

Razborov olyan áramköröket elemzett, amelyek csak ÉS és VAGY kapukat tartalmaznak, és bizonyított hogy egy adott függvényt nehéz volt kiszámítani ilyen áramkörök segítségével, függetlenül attól, hogy a kapuk hogyan vannak elrendezve – mi több, ez a függvény köztudottan NP-teljes. A kutatóknak csak annyit kellett tenniük, hogy feloldják a P versus NP-t, Razborov technikáit kiterjesztették a NEM kapukkal rendelkező áramkörökre.

„Volt egyfajta egyetemes érzés, hogy még egy lépés, még egy csapás, és meg fogjuk érni” – mondta Razborov. De nem ez történt. Maga Razborov bebizonyította, hogy módszere kudarcot vall, ha NEM gates kerül a keverékbe, és senki sem találna más utat. Ahogy teltek az évek, azon kezdett töprengeni, hogy vajon miért fogyott el az ösvény.

Az Egyesült Államokban Rudich ugyanezen a kérdésen töprengett. Ő és Impagliazzo egyetemi osztálytársak voltak, akik együtt végeztek érettségit. Barátságukat Gödel és Turing önreferenciális bizonyításai iránti közös elragadtatás váltotta ki, valamint ezeknek a matematika és számítástechnika alapjaira gyakorolt ​​hatásai.

"Az volt a viccünk, hogy kapunk egy gombot, amelyen az állt, hogy "önhivatkozás" - mondta Impagliazzo.

Végzős hallgatóként Rudich és Impagliazzo is a kriptográfia komplexitáselméleti alapjain dolgozott, ez a téma talán a legjobb gyakorlati motivációt kínálja a P ≠ NP bizonyítására. A kriptográfusok úgy rejtik el a titkos üzeneteket, hogy „álvéletlenségbe” álcázzák azokat – az így titkosított üzenetek véletlenszerű számok zűrzavarának tűnnek bármely lehallgató számára, de a címzett mégis meg tudja dekódolni. De hogyan lehetsz biztos abban, hogy egy lehallgatónak túl nehéz lesz feltörni a kódot?

Itt jön a képbe a komplexitáselmélet. A ma legszélesebb körben használt titkosítási módszerek mind látszólag nehéz NP-problémákon alapulnak – az üzenet visszafejtéséhez a támadónak egy még fel nem fedezett gyors algoritmusra van szüksége a probléma megoldásához. Annak megállapításához, hogy ezek a módszerek valóban biztonságosak, egy dolgot kell tennie, hogy be kell bizonyítania, hogy P ≠ NP. Sipser szerint bizonyíték nélkül nem lehet mást tenni, mint „reménykedni, hogy aki előtt titkolni akarod, az nem jobb matematikus, mint te”.

Bár önmagában lenyűgöző volt, a kriptográfia távol áll az önreferenciális érvektől, amelyek először vonták be Rudichot és Impagliazzót a pályára. De miközben Rudich küzdött, hogy megértse, miért akadt meg az áramkör komplexitásának megközelítése, kezdett rájönni, hogy a két alany mégsem áll olyan messze egymástól. A stratégiát kutató kutatók arra törekedtek, hogy bebizonyítsák, hogy P ≠ NP önpusztító karaktere emlékeztet Gödel híres tételére, „ez az állítás bizonyíthatatlan” – és a kriptográfia segíthet megmagyarázni, miért. Oroszországban Razborov hasonló összefüggést fedezett fel nagyjából ugyanebben az időben. Ezek voltak a természetes bizonyítékok gátjának magvai.

A természetes bizonyítási gát középpontjában az a feszültség, hogy a nagy komplexitású függvények és az alacsony bonyolultságú függvények megkülönböztetése hasonló ahhoz a feladathoz, hogy megkülönböztessük a valódi véletlenszerűséget az üzenetek titkosítására használt pszeudovéletlenségtől. Szeretnénk bemutatni, hogy a nagy komplexitású függvények kategorikusan különböznek az alacsony komplexitású függvényektől, bizonyítandó, hogy P ≠ NP. De azt is szeretnénk, ha a pszeudovéletlenség megkülönböztethetetlen lenne a véletlenszerűségtől, és bíznánk a kriptográfia biztonságában. Lehet, hogy nem tudjuk mindkét irányba.

Kegyetlen vicc

1994-ben Razborov és Rudich rájött, hogy hasonló meglátásokra jutottak, és elkezdtek együtt dolgozni, hogy egyesítsék eredményeiket. Először is megfigyelték, hogy az összes korábbi kísérlet P ≠ NP bizonyítására az áramkör komplexitásával ugyanazt az általános stratégiát követte: azonosítsa egy NP-teljes Boole-függvény egy speciális tulajdonságát, majd bizonyítsa be, hogy egyetlen könnyen kiszámítható függvény sem oszthatja meg ezt a tulajdonságot. Ez azt mutatná, hogy a választott NP-teljes függvényt valóban nehéz volt kiszámítani, bizonyítva, hogy P ≠ NP.

Sipser, Razborov és mások sikeresen alkalmazták ugyanezt a stratégiát korlátozottabb eredményeik bizonyítására, és minden esetben a kutatók által azonosított különleges tulajdonság a legtöbb Boole-függvényen megosztott. Razborov és Rudich megalkotta a „természetes bizonyíték” kifejezést arra az esetre utalva, amikor az ingatlant széles körben megosztották, egyszerűen azért, mert nem volt ismert alternatíva. Ha „természetellenes” bizonyítékok lehetségesek lennének, nagyon ellentmondónak kellene lenniük, és megérdemelnék a nevet.

Razborov és Rudich ezután bebizonyította fő eredményét: a P ≠ NP természetes bizonyításához nagyon átfogó megértésre lenne szükség, hogy miben különböznek egymástól a könnyen kiszámítható és nehezen kiszámítható függvények, és ez a tudás egy gyors algoritmushoz is hozzájárulhat a könnyű felismeréshez. -függvények kiszámítása még akkor is, ha felületesen bonyolultak. Ha a komplexitáselméleti szakembereknek sikerült volna P ≠ NP természetes bizonyítása, akkor felfedeztek volna egy szinte tévedhetetlen módot arra, hogy egy tetszőleges igazságtáblázatra pillantsanak, és megállapítsák, hogy a megfelelő függvénynek magas vagy alacsony az áramköri komplexitása – ez sokkal erősebb és általánosabb eredmény, mint bizonyítani akarták.

– Szinte nem is tehetsz többet, mint amennyit megalkudtál – mondta Carmosino.

Mintha egy konkrét állítás tényét próbálta volna ellenőrizni, de minden kísérlet egy általános célú hazugságvizsgáló tervrajzává vált – túl szépnek tűnik, hogy igaz legyen. A komplexitáselméleti szakemberek számára a természetes bizonyítékok meglepő ereje szintén kevésbé valószínűvé tette a sikert. De ha egy ilyen bizonyítás sikerült volna, akkor a váratlan következmények rossz hírek lennének a kriptográfia számára, az áramkör bonyolultsága és a pszeudovéletlenség közötti kapcsolat miatt.

Ennek az összefüggésnek a megértéséhez képzeljük el, hogy megnézzük a kimeneti oszlopot egy Boole-függvény igazságtáblázatában sok bemeneti változóval, és minden „igaz”-ot 1-re, minden „hamis”-t 0-ra cserélünk:

Ha a Boole-függvénynek nagy az áramkör bonyolultsága, akkor a kimenetek hosszú listája elvileg megkülönböztethetetlen lesz egy valóban véletlenszerű 0-tól és 1-től – például egy érme többszöri feldobásával kapott értéktől. De ha a függvénynek alacsony az áramkör bonyolultsága, akkor a karakterláncnak egyszerű, tömör leírással kell rendelkeznie, még akkor is, ha bonyolultnak tűnik. Ez nagyon hasonlít a kriptográfiában használt pszeudovéletlen karakterláncokhoz, amelyek tömör leírása a látszólagos véletlenségbe temetett titkos üzenet.

Tehát Razborov és Rudich eredménye azt mutatta, hogy a P ≠ NP bármely természetes bizonyítása egy gyors algoritmust is eredményez, amely képes megkülönböztetni a rejtett üzeneteket tartalmazó pszeudovéletlen karakterláncokat a valóban véletlenszerűektől. A biztonságos kriptográfia lehetetlen lenne – pontosan az ellenkezője annak, amit a kutatók a P ≠ NP bizonyításával reméltek megállapítani.

Másrészt, ha lehetséges a biztonságos kriptográfia, akkor a természetes bizonyítások nem életképes stratégia a P ≠ NP bizonyítására – ez a biztonságos kriptográfia előfeltétele. Dióhéjban ez a természetes bizonyítási korlát. Úgy tűnt, hogy a komplexitáselméleti szakemberek egy kegyetlen tréfát kaptak.

„Ha hiszel a keménységben, akkor hidd el, hogy nehéz bizonyítani a keménységet” – mondta Kabanets.

A Metaverse -be

Ez a kapcsolat a P ≠ NP sejtés következményei és a bizonyítás nehézsége között érdekes volt, de nehéz volt megállapítani. Egyrészt a természetes bizonyítási korlát csak egy megközelítést akadályozott meg a P ≠ NP bizonyítására. Másrészt a P ≠ NP bizonyításának nehézségét nem magával a P ≠ NP-vel, hanem a biztonságos kriptográfia létezésével kapcsolta össze – ez egy szorosan kapcsolódó, de nem teljesen egyenértékű probléma. Ahhoz, hogy valóban megértsék az összefüggést, a kutatóknak meg kell felelniük a meta-komplexitásnak.

„Van ez az intuíció, hogy „ó, mert P ≠ NP, nehéz bizonyítani, hogy P ≠ NP” – mondta Williams. „De ahhoz, hogy értelmet nyerjünk ennek az intuíciónak, el kell kezdenünk azon a feladaton gondolkodni, hogy a P ≠ NP-hez hasonló dolgokat számítási problémaként bizonyítsunk.”

Ezt tette Kabanets végzős hallgatóként. Ukrajnában nőtt fel, és két évvel a Szovjetunió bukása után fejezte be számítástechnikai alapképzését. Az ezt követő zűrzavarban kevés lehetősége volt az őt leginkább érdeklő elméleti témákkal foglalkozni.

„Valami akadémikusabbat akartam csinálni” – emlékezett vissza Kabanets. "És arra is kíváncsi voltam, hogy lássam a világot." Kanadába költözött, hogy érettségizett, és ott tanulta meg a természetes bizonyítási akadályt. Carmosinóhoz hasonlóan Kabanets is le volt nyűgözve az eredménytől. „Nagyon mélynek tűnt, hogy köztetek van ez a kapcsolat” – mondta.

2000-ben, az érettségi vége felé azt tapasztalta, hogy a természetes bizonyítási akadályok folyamatosan előkerülnek a vele folytatott beszélgetései során. Jin-Yi Cai, egy komplexitáselméleti szakember, aki akkoriban Torontóba látogatott szombaton. Kezdték a sorompót nem útlezárásnak, hanem felhívásnak tekinteni – lehetőséget arra, hogy pontosan megvizsgálják, milyen nehéz is keményen bizonyítani a problémákat. A papír amelyben ezt az új perspektívát fektették le, az egyik legbefolyásosabb korai alkotás lesz a meta-komplexitás születőben lévő területén.

Kabanets és Cai írása rávilágított egy számítási problémára, amely a természetes bizonyítási gát Razborov és Rudich megfogalmazásában rejlik: Adott egy Boole-függvény igazságtáblázata, határozza meg, hogy magas vagy alacsony az áramkör bonyolultsága. Ezt a minimális áramkörméret problémának, vagy MCSP-nek nevezték el.

Az MCSP egy alapvető meta-komplexitási probléma: olyan számítási probléma, amelynek tárgya nem a gráfelmélet vagy más külső téma, hanem maga a komplexitáselmélet. Valójában ez olyan, mint annak a kérdésnek a kvantitatív változata, amely arra késztette a komplexitáselméleti szakembereket, hogy az 1980-as években az áramköri komplexitási megközelítést alkalmazva a P versus NP-vel foglalkozzanak: Mely Boole-függvényeket nehéz kiszámítani, és melyeket könnyű?

„Ha kitalálunk egy MCSP-algoritmust, az olyan lenne, mint automatizálni azt, amit a komplexitáselméletben csinálunk” – mondta Impagliazzo. "Legalább hatalmas betekintést kell adnunk abba, hogyan végezzük jobban a munkánkat."

A komplexitáselméleti szakemberek nem aggódnak amiatt, hogy ez a varázslatos algoritmus kiiktatja őket a munkából – szerintük egyáltalán nem létezik, mert Razborov és Rudich kimutatta, hogy minden ilyen algoritmus, amely megkülönbözteti a nagy bonyolultságú igazságtáblázatokat az alacsony bonyolultságúaktól, kriptográfiát jelent. lehetetlen. Ez azt jelenti, hogy az MCSP valószínűleg nehéz számítási probléma. De mennyire nehéz? NP-teljes, mint a Hamilton-út probléma és szinte minden más probléma, amellyel a kutatók küzdöttek az 1960-as években?

Az NP-vel kapcsolatos problémák esetén „mennyire nehéz?” általában elég könnyű válaszolni, de az MCSP furcsa kiugró értéknek tűnt. „Nagyon kevés olyan „lebegő” problémánk van, amely nem kapcsolódik az NP-teljes problémák szigetéhez, még akkor is, ha nehéznek tűnik” – mondta Kabanets.

Kabanets tudta, hogy nem ő és Cai voltak az elsők, akik fontolóra vették az általuk MCSP-nek nevezett problémát. A szovjet matematikusok az 1950-es évektől kezdődően egy nagyon hasonló problémát tanulmányoztak, korai kísérletként, hogy megértsék a különböző számítási problémák belső nehézségeit. Leonid Levin birkózott vele, miközben az 1960-as évek végén kidolgozta azt az elméletet, amely az NP-teljesség elméletévé vált, de nem tudta NP-teljesen bebizonyítani, és enélkül adta ki alapvető tanulmányát.

Ezt követően a probléma 30 évig kevés figyelmet kapott, mígnem Kabanets és Cai fel nem jegyezte a természetes bizonyítási korláttal való kapcsolatát. Kabanets nem számított arra, hogy maga dönti el a kérdést – ehelyett azt akarta feltárni, miért volt olyan nehéz bebizonyítani, hogy ez a látszólag nehéz probléma a számítási keménységgel kapcsolatban valóban nehéz.

„Ez bizonyos értelemben meta-meta-komplexitás” – mondta Rahul Santhanam, az Oxfordi Egyetem komplexitáselmélete.

De vajon a keménység egészen lefelé volt, vagy volt legalább valami módja annak megértésére, hogy a kutatóknak miért nem sikerült bebizonyítaniuk, hogy az MCSP NP-teljes? Kabanets felfedezte, hogy igen, ennek megvan az oka: az áramkör bonyolultságának megértésének nehézsége akadályként hat az MCSP NP-teljességének bizonyítására szolgáló ismert stratégiák elé – ez a probléma önmagában az áramkör bonyolultságának megértésének nehézségeivel kapcsolatos. A természetes bizonyítási korlát torz, önpusztító logikája megkerülhetetlennek tűnt.

Az is lehetséges, hogy az MCSP nem NP-teljes, de ez is valószínűtlennek tűnik – a probléma bizonyos egyszerűbb változatairól már ismert, hogy NP-teljesek.

„Egyszerűen nincs olyan hely, ahol ezt közvetlenül össze lehetne kapcsolni az általunk vizsgált többi problémával” – mondta Impagliazzo.

Kabanets rávilágított az MCSP furcsa viselkedésére, de nem tudta, hogyan haladjon tovább. A metakomplexitás kutatása lelassult. 16 évvel később ismét virágzott, amikor a kutatók meglepő összefüggést fedeztek fel egy másik alapvető kérdéssel: Mennyire nehéz megoldani a problémákat, ha az idő nagy részében csak a helyes válasz megszerzése érdekel?

War of the Worlds

A mindennapi problémákra a legtöbbször működő válaszok gyakran elég jók. Ingázásainkat például tipikus forgalmi minták szerint tervezzük, nem pedig a legrosszabb forgatókönyvekre.

A legtöbb komplexitáselméleti szakembert nehezebb kielégíteni: csak akkor elégednek meg azzal, hogy egy problémát könnyűnek nyilvánítanak, ha találnak egy gyors algoritmust, amely minden lehetséges bemenetre a megfelelő választ kapja. Ez a standard megközelítés a problémákat a „legrosszabb eset” komplexitás szerint osztályozza. De létezik az „átlagos esetek” összetettségének elmélete is, amely szerint a problémákat könnyűnek tekintik, ha van egy gyors algoritmus, amely a legtöbb bemenetre a megfelelő választ kapja.

A megkülönböztetés fontos a kriptográfusok számára. Képzeljen el egy számítási problémát, amelyet szinte minden bemenetre könnyű megoldani, kivéve néhány makacs esetet, amikor a legjobb algoritmus meghibásodik. A legrosszabb eset komplexitáselmélete ezt nehéz problémának tekinti, de a kriptográfia számára haszontalan: ha csak néhány üzenetét nehéz megfejteni, mi értelme van?

Valójában Levin kezdeményezte az átlagos esetek összetettségének szigorú tanulmányozását, egy évtizeddel az NP-teljességgel kapcsolatos úttörő munkája után. A közbeeső években összetűzésbe került a szovjet hatóságokkal – tiszteletlen bajkeverő volt, aki időnként aláásta a hazafias tevékenységet a kommunista párt ifjúsági csoportjában. 1972-ben kifejezetten politikai okokból megtagadták tőle a doktori címet.

"Ahhoz, hogy fiatal kutatóként sikeres legyél a Szovjetunióban, nem lehetsz túlzottan elgondolkodtató, és nehéz elképzelni, hogy Leonyid ne legyen véleményes" - mondta Impagliazzo.

Levin 1978-ban emigrált az Egyesült Államokba, és az 1980-as évek közepén az átlagos esetek bonyolultsága felé fordult. Másokkal együtt kezdett dolgozni az elmélet továbbfejlesztésén, köztük Impagliazzóval, aki akkoriban végzett. Ám bár haladtak előre, Impagliazzo úgy találta, hogy a kutatók gyakran elbeszéltek egymás mellett. Mindenkit egy lapra akart hozni, és az sem segített, hogy Levin papírjai híresen tömörek voltak – az kezdeményezte a terepet az átlagos kis- és nagybetűk összetettsége két oldalnál rövidebb volt.

„Lefordítani akartam Leonyid munkáját érthetőbb szakkifejezésekre” – mondta Impagliazzo. Úgy döntött, hogy egy rövid, játékos áttekintéssel kezdi az átfogó képet, mielőtt belemerül a matematikába. – Ez a fajta átvette az újságot, és amúgy is ez az egyetlen rész, amelyre bárki emlékszik.

A papírAz 1995-ben megjelent, azonnali klasszikussá vált. Impagliazzo szeszélyes neveket talált ki öt világ különböző fokú számítási keménységgel és különböző kriptográfiai képességekkel különböztethetők meg. Ezen világok egyikében élünk, de nem tudjuk, melyikben.

Amióta Impagliazzo cikke megjelent, a kutatók arról álmodoztak, hogy kiiktatják miniatűr multiverzumának egyes részeit – szűkítik a lehetőségek terét azáltal, hogy bebizonyítják, hogy egyes világok mégsem lehetségesek. Két világ különösen csábító célpont: azok, ahol a titkosítás lehetetlen, bár P ≠ NP.

Az egyik ilyen világban, az úgynevezett Heuristica-ban, minden NP-teljes probléma könnyen megoldható a legtöbb bemeneten, de a gyors algoritmusok időnként hibáznak, így ezeket a problémákat még mindig nehéznek tekintik a legrosszabb eset komplexitáselmélete szerint. Ez az a világ, amelyben a titkosítás lehetetlen, mert szinte minden kód könnyen feltörhető. A másik világban, az úgynevezett Pessilandban a titkosítás más okból lehetetlen: minden probléma átlagos értelemben nehéz, de az üzenet titkosítása még a címzett számára is olvashatatlanná teszi.

Ez a két világ szorosan összefügg a meta-komplexitási problémákkal – különösen a Heuristica sorsa kapcsolódik ahhoz a régóta fennálló kérdéshez, hogy az MCSP NP-teljes-e. A kérdés, amely olyan régen lenyűgözte Kabanets-t, és megdöbbentette Levint, nem puszta kíváncsiság: egy egész világ forog kockán.

A Heuristica kizárásához a kutatóknak meg kell rontani a különbséget a legrosszabb eset és az átlagos eset bonyolultsága között – vagyis be kell bizonyítaniuk, hogy minden olyan hipotetikus algoritmus, amely a legtöbb bemeneten helyesen oldja meg az NP-teljes problémát, valóban meg tudja oldani. minden esetben. Ez a fajta kapcsolat, amelyet a legrosszabb eset és az átlagos eset közötti redukciónak neveznek, ismert bizonyos problémák esetén, de egyik sem NP-teljes, így ezek az eredmények nem utalnak semmi általánosabbra. A Heuristica megszüntetése félúton vezetné a kriptográfusokat a biztonságos titkosítás álmának megvalósításához, azon az egyetlen feltételezésen alapulóan, hogy P ≠ NP.

De egy világ tönkretétele nem kis teljesítmény. 2003-ban két komplexitáselméleti szakember kimutatta, hogy az ismert NP-teljes problémák esetében a legrosszabb esetek és az átlagos esetek közötti csökkentések bizonyítására irányuló jelenlegi megközelítések rendkívüli következményekkel járnának, ami arra utal, hogy az ilyen bizonyítások valószínűleg nem lehetségesek.

A kutatóknak más megközelítést kellene találniuk, és most úgy gondolják, hogy az MCSP lehet az a probléma, amire szükségük van. De ez több mint egy évtizedig nem derült ki. A kapcsolat első pillantása Marco Carmosinonak a természetes bizonyítékok akadálya iránti tartós elbűvölésében merült fel.

Carmosino végzős hallgatóként találkozott először a metakomplexitás kutatásával a 2013 papír Kabanets és négy másik kutató, akik továbbfejlesztették a természetes bizonyítási korlát megközelítését, amelyet Kabanets több mint egy évtizeddel korábban úttörőként vezetett be. Ez csak megerősítette meggyőződését, hogy még mindig van mit tanulni Razborov és Rudich klasszikus dolgozatából.

„Akkoriban megszállott voltam ennek a papírnak” – mondta Carmosino. "Semmi sem változott."

A megszállottság végül meghozta gyümölcsét, amikor a Kaliforniai Egyetemen, Berkeleyben egy féléves workshopon tett látogatást, ahol ideje nagy részét Impagliazzóval, Kabanets-szel és Antonina Kolokolova, a Memorial University of Newfoundland komplexitáselméleti szakértője, aki Kabanetsszel együttműködött a 2013-as tanulmány elkészítésében. Carmosino már egyszer dolgozott együtt hármukkal, és ez a sikeres együttműködés önbizalmat adott neki ahhoz, hogy kérdéseket tegyen fel az őt leginkább lenyűgöző témával kapcsolatban.

„Jó értelemben ingerelte az embereket” – emlékezett vissza Kabanets.

Carmosinónak eleinte új ötletei voltak az MCSP változatának NP-teljességének bizonyítására, amely Razborov és Rudich természetes bizonyítási korlátról szóló tanulmányában jelent meg. De ezek az ötletek nem váltak be. Ehelyett Impagliazzo nem mindennapi megjegyzése ráébreszti a négy kutatót, hogy a természetes bizonyítási korlát erősebb algoritmusokat eredményezhet, mint bárki gondolta volna – az útlezárásba egy titkos térképet véstek.

egy 2016 papír, a négy kutató bebizonyította, hogy egy bizonyos fajta átlagos MCSP-algoritmus felhasználható a legrosszabb eset algoritmusának megalkotására a véletlenszerű számjegysorozatokban elrejtett minták azonosítására – ezt a feladatot az informatikusok „tanulásnak” nevezik. Lenyűgöző eredmény, mert az intuitív tanulás nehezebbnek tűnik, mint az MCSP-algoritmus által végrehajtott bináris osztályozási feladat – nagy vagy alacsony bonyolultságú. És meglepő módon összekapcsolta az egyik feladat legrosszabb összetettségét a másik feladat átlagos összetettségével.

„Nem volt nyilvánvaló, hogy egyáltalán létezik ilyen kapcsolat” – mondta Impagliazzo.

Az MCSP gyors algoritmusa pusztán hipotetikus az általános Boole-áramkörök esetében: nem létezhet, hacsak az MCSP nem bizonyul egyszerű számítási problémának, annak ellenére, hogy minden ellenkező bizonyíték van, és ez azt jelenti, hogy a négy kutató tanulmánya által feltételezett tanulási algoritmus ugyanolyan hipotetikus.

De az MCSP néhány egyszerűbb verziójához – a nagy bonyolultságú igazságtáblázatok megkülönböztetése az alacsony bonyolultságúaktól, amikor az áramkörökre specifikus korlátozások vonatkoznak – a gyors algoritmusok sok éve ismertek. Carmosino, Impagliazzo, Kabanets és Kolokolova tanulmánya kimutatta, hogy ezek az algoritmusok olyan tanulási algoritmusokká alakíthatók, amelyek ugyancsak korlátozottak, de még mindig erősebbek, mint a kutatók korábban ilyen szigorú elméleti szinten.

„Valahogy az önreferenciális ízük lehetővé teszi olyan dolgok megtételét, amelyeket látszólag nem tud megtenni szokásosabb problémákkal” – mondta Ilango.

Az eredmény felkeltette a komplexitáselmélet más témákkal foglalkozó kutatóinak figyelmét. Ez egyben a meta-komplexitás és az átlagos esetkomplexitás közötti további összefüggések előzetese is volt, amelyek az elkövetkező években fognak megjelenni.

Leginkább arról tanúskodik, hogy a kutatók milyen messzire juthatnak el, ha egyszerű kérdéseket tesznek fel olyan akadályokról, amelyek eleinte csak akadályozzák a fejlődésüket.

„Ez a fajta kettősség a komplexitás elmúlt 30 vagy 40 évének egyik témája” – mondta Impagliazzo. "Az akadályok gyakran a lehetőségek."

Részleges hitel

A haladás csak felgyorsult az elmúlt években, amióta Carmosino és kollégái publikálták az újságot.

„Új dolgok történnek” – mondta Kolokolova. „Rengeteg igazán, nagyon tehetséges fiatal kutató van.”

Ilango egyike ezeknek a fiatal kutatóknak – a posztgraduális iskola első három évében megtámadta azt a ijesztő nyitott problémát, hogy az MCSP NP-teljességét kétirányú stratégiával bizonyítsa: az NP-teljesség bizonyítása egyszerűbb verzió az MCSP-t, ahogyan azt az áramkör-bonyolítás kutatói tették, amikor az 1980-as években megtámadták a P-t az NP-vel szemben, miközben bebizonyították az NP-teljességet bonyolultabb változatai, amelyek intuitív módon nehezebbnek tűnnek, és így talán könnyebb keményen bizonyítani.

Ilango a meta-komplexitás iránti érdeklődésének tulajdonítja Eric Allender, a Rutgers Egyetem komplexitáselmélete, és azon kevés kutatók egyike, akik a 2000-es években és a 2010-es évek elején folytatták a metakomplexitás kutatását. „A lelkesedése ragadós volt” – mondta Ilango.

Egy másik fiatal kutató, akit Allender ihletett, az Shuichi Hirahara, jelenleg a Tokiói Nemzeti Informatikai Intézet professzora. Hirahara 2018-ban még végzős hallgatóként felfedte a meta-komplexitás és az átlagos esetkomplexitás közötti kapcsolat valódi mértékét, amelyet Carmosino és szerzőtársai fedeztek fel. Ez a négy kutató összefüggést talált egy probléma – az MCSP – átlagos összetettsége és egy másik – a logikai tanulás – legrosszabb esete között. Hirahara továbbfejlesztette technikájukat származik az MCSP esetében a legrosszabb esettől az átlagosig terjedő csökkentés. Eredménye azt sugallja, hogy egy hipotetikus átlagos esetű MCSP-algoritmus, mint amilyet Carmosino és kollégái gondoltak, valójában elég erős lenne ahhoz, hogy hiba nélkül megoldja az MCSP egy kicsit más változatát.

Hirahara eredménye azért izgalmas, mert sok kutató azt gyanítja, hogy az MCSP NP-teljes, ellentétben minden más olyan problémával, amelyre a legrosszabb esettől az átlagosig terjedő csökkenés ismert. Ha ki tudják terjeszteni Hirahara eredményeit az összes átlagos eset algoritmusára, majd bebizonyítják, hogy az MCSP NP-teljes, az azt bizonyítaná, hogy nem a Heuristicában élünk.

„Ez valóban megrázó eredmény lenne” – mondta Santhanam.

Annak bizonyítása, hogy az MCSP NP-teljes, nehéz feladatnak tűnhet – elvégre a kérdés már több mint 50 éve nyitott. De miután a áttörés tavaly Hirahara, a kutatók most sokkal közelebb kerültek, mint azt néhány évvel ezelőtt bárki várta volna.

Hirahara bizonyította az NP-teljességet a probléma részleges MCSP-nek nevezett változatánál, amelyben figyelmen kívül hagyja az egyes igazságtáblázatok bizonyos bejegyzéseit. Bizonyítása az Ilango által kifejlesztett módszerekre épült annak bizonyítására, hogy a részleges MCSP egyenértékű egy látszólag független problémával, amely magában foglalja a titkos megosztásnak nevezett kriptográfiai technikát. Ez egy módja annak, hogy egy titkosított üzenetet sok ember között feloszthassunk, így csak akkor lehet dekódolni, ha egy bizonyos töredék együtt működik.

Bármilyen valós kriptográfiai alkalmazás esetén érdemes előre tudni ezt a töredéket, de extra kriptográfiai trükkök segítségével olyan frusztráló forgatókönyvet készíthet, amelyben nehéz kitalálni, hány embernek kell együttműködnie. Hirahara megtalálta a módját annak bizonyítására, hogy ez a kitalált kriptográfiai probléma NP-teljes volt, majd megmutatta, hogy a bizonyítás magában foglalja a részleges MCSP NP-teljességét is.

Ez az eredmény még jobban felvillanyozta a metakomplexitás kutatóit, mint Hirahara korábbi munkái, és más kutatók is felfigyeltek erre – Lance Fortnow komplexitáselméleti szakember és blogger ezt a év eredménye. Ennek az az oka, hogy a számítási problémák ilyen „részfüggvényes” változatainak kezelése kulcsfontosságú köztes lépés volt más NP-teljességi bizonyításokban.

„Csodálatos munka” – mondta Williams. „Mindenki azt gondolta, hogy ezek a részproblémák nagyjából ugyanolyan nehézségűek, mint a teljes probléma.”

Továbbra is akadályok vannak az MCSP teljes verziójának NP-teljességének bizonyítása előtt. De egyik sem olyan akadály, amely arra utalna, hogy teljesen új eszköztárra van szükség – lehet, hogy csak az ismert technikák kombinálásának megfelelő módját kell megtalálni. Egy bizonyíték végre rendezné azon kevés probléma egyikének státuszát, amelyek az összetettségelmélet fennállása óta ellenálltak az osztályozásnak. Levin ezt írta e-mailben: „Megalázna, ha kimutatnám, hogy hülye vagyok, amiért nem láttam :-)”

A hiányzó darabok

Még csak nem is az MCSP az egyetlen meta-komplexitási probléma, amely jelentős áttörést eredményezett. 2020-ban a Cornell Tech kriptográfusa Rafael Pass és végzős hallgatója Yanyi Liu összefüggést fedezett fel egy másik meta-komplexitási probléma és egy alapvető kriptográfiai protokoll között, amely meghatározza a határt a Heuristica és a Pessiland között, Impagliazzo legrosszabb világa között (ahol az NP-teljes problémák átlagos értelemben nehézek, de a kriptográfia még mindig lehetetlen). Ez teszi a vizsgált problémát a Pessiland elleni támadás első számú jelöltjévé, és az övék újabb munkák azt jelzi, hogy a Heuristica ellen is működhet.

– A kirakós játék különböző részei hiányoznak – mondta Pass. „Számomra varázslatos, hogy ezek a mezők olyan szorosan kapcsolódnak egymáshoz.”

Hirahara figyelmeztet, hogy még mindig kihívások várnak azokra a kutatókra, akik az Impagliazzo által 30 évvel ezelőtt megidézett világokat akarják kiirtani. "Szeretném azt mondani, hogy egy bizonyos ponton a Heuristica és a Pessiland kizárásra kerül, de nem tudom, mennyire vagyunk közel" - mondta.

Sok kutató arra számít, hogy a legnagyobb nehézséget a látszólag ártalmatlan szakadék áthidalása jelenti az átlagos eset összetettségének két különböző modellje között. A kriptográfusok általában átlagos esetszámú algoritmusokat tanulmányoznak, amelyek mindkét irányban hibáznak, alkalmanként véletlenszerű karakterláncokat álvéletlennek neveznek, és fordítva. A Hirahara a legrosszabb esetből az átlagosra csökkentései eközben olyan átlagos esetekre vonatkozó algoritmusoknál működnek, amelyek csak az első típusú hibát követik el. Az ehhez hasonló finom megkülönböztetések a komplexitáselmélet világában változtathatnak. De ennek az akadálynak és sok másnak ellenére Allender nem tehet mást, mint egy őrzött optimizmust.

„Igyekszem nem hagyni, hogy túlságosan hívő legyek, mert elég jól bevált tapasztalatok vannak arról, hogy semmi sem működik” – mondta. „De nagyon sok izgalmas fejleményt látunk – olyan módszereket, amelyekkel legyőzhetjük a korlátoknak tűnő dolgokat.”

Ha van egy leckét, amit a kutatók levontak a P versus NP kérdés megválaszolása – vagy akár csak annak megértése – küzdelmeiből, az az, hogy a komplexitáselmélet maga is összetett. De éppen ez a kihívás teszi olyan kifizetődővé a küldetést.

„Valójában nagyszerű, hogy ilyen nehéz” – mondta Carmosino. – Soha nem fogok unatkozni.

A szerkesztő megjegyzése: Scott Aaronson tagja a Quanta Magazine'S Tanácsadó Testület.