50-letno potovanje teorije kompleksnosti do meja znanja | Revija Quanta

V prvem tednu jesenskega semestra leta 2007 se je Marco Carmosino odvlekel na tečaj matematike, potreben za vse smeri računalništva na Univerzi Massachusetts, Amherst. Carmosino, študent drugega letnika, je razmišljal, da bi opustil fakulteto, da bi oblikoval video igre. Nato je profesor postavil preprosto vprašanje, ki bo spremenilo tok njegovega življenja: Kako veste, da matematika dejansko deluje?

"Zaradi tega sem se usedel in bil pozoren," se spominja Carmosino, zdaj teoretični računalniški znanstvenik pri IBM. Prijavil se je na izbirni seminar o delu Kurta Gödela, čigar vrtoglavi samoreferenčni argumenti so prvi razkrili meje matematičnega razmišljanja in ustvarili osnovo za vse prihodnje delo o temeljnih mejah računanja. Bilo je veliko za sprejeti.

"100-odstotno nisem razumel," je dejal Carmosino. "Ampak vedel sem, da si želim."

Danes tudi izkušenim raziskovalcem primanjkuje razumevanja, ko se soočijo z osrednjim odprtim vprašanjem v teoretični računalniški znanosti, znanim kot problem P proti NP. V bistvu se to vprašanje sprašuje, ali je številne računalniške probleme, ki so dolgo veljali za izjemno težke, dejansko mogoče enostavno rešiti (prek skrivne bližnjice, ki je še nismo odkrili) ali pa so, kot sumi večina raziskovalcev, res težki. Na kocki ni nič manj kot narava tega, kar je mogoče spoznati.

Kljub desetletjem prizadevanj raziskovalcev na področju teorije računalniške kompleksnosti - preučevanje takih vprašanj o intrinzični težavnosti različnih problemov - je rešitev vprašanja P proti NP ostala nedosegljiva. In sploh ni jasno, kje naj se začne morebitni dokaz.

"Ni načrta," je rekel Michael Sipser, veteran teoretik kompleksnosti na Tehnološkem inštitutu v Massachusettsu, ki se je leta 1980 ukvarjal s problemom. "Kot bi šel v divjino."

Zdi se, da je dokazovanje, da je računalniške probleme težko rešiti, samo po sebi težka naloga. Toda zakaj je tako težko? In kako težko je? Carmosino in drugi raziskovalci na podpolju metakompleksnosti preoblikujejo taka vprašanja kot računalniške probleme, s čimer poganjajo področje naprej tako, da obrnejo lečo teorije kompleksnosti nazaj vase.

»Morda si mislite, 'OK, to je nekako kul. Mogoče so teoretiki kompleksnosti ponoreli,« je dejal Rahul Ilango, podiplomski študent na MIT, ki je ustvaril nekaj najbolj razburljivih nedavnih rezultatov na tem področju.

S preučevanjem teh vase usmerjenih vprašanj so raziskovalci ugotovili, da je težko dokazovanje računalniške trdote tesno povezano s temeljnimi vprašanji, ki se na prvi pogled morda zdijo nepovezana. Kako težko je opaziti skrite vzorce v navidezno naključnih podatkih? In če resnično težki problemi obstajajo, kako pogosto so težki?

"Postalo je jasno, da je metakompleksnost blizu bistva stvari," je dejal Scott Aaronson, teoretik kompleksnosti na Univerzi v Teksasu v Austinu.

To je zgodba o dolgi in vijugasti poti, ki je vodila raziskovalce od problema P proti NP do metazapletenosti. Pot ni bila lahka – pot je posejana z lažnimi zavoji in cestnimi zaporami in vedno znova se vije nazaj. Toda za raziskovalce metakompleksnosti je to potovanje v neznano pokrajino nagrada. Začnite postavljati na videz preprosta vprašanja, je rekel Valentin Kabanets, teoretik kompleksnosti na univerzi Simon Fraser v Kanadi, in "nimate pojma, kam boste šli."

Znano neznano

Problem P proti NP ima svoje bledo ime zaradi navade teoretikov kompleksnosti, da računalniške probleme razvrščajo v široke "razredi zahtevnosti” z nalepkami, ki nakazujejo simbole Nasdaq ticker. Računski problem je tisti, ki ga je načeloma mogoče rešiti z algoritmom - natančno določenim seznamom navodil. Vendar niso vsi algoritmi enako uporabni in razlike med algoritmi namigujejo na temeljne razlike med problemi v različnih razredih. Izziv za teoretike kompleksnosti je spremeniti te namige v stroge izreke o odnosih med razredi kompleksnosti.

Ta razmerja odražajo nespremenljive resnice o računanju, ki daleč presegajo katero koli specifično tehnologijo. "To je kot odkrivanje zakonov vesolja," je dejal Kabanets.

»P« in »NP« sta najbolj znana člana a rastoča menažerija več sto kompleksnih razredov. Grobo rečeno, P je razred problemov, ki jih je mogoče zlahka rešiti, kot je abecedno urejanje seznama. NP je razred problemov z enostavno preverljivimi rešitvami, kot so uganke sudoku. Ker so vsi lahko rešljivi problemi tudi lahko preverljivi, so problemi v P tudi v NP. Vendar se zdi, da je nekatere težave z NP težko rešiti – ne morete takoj zaznati rešitve sudokuja, ne da bi prej preizkusili veliko možnosti. Ali je mogoče, da je ta navidezna trdota le iluzija - da obstaja en sam preprost trik za rešitev vsake zlahka preverljive težave?

Če je tako, potem je P = NP: oba razreda sta enakovredna. Če je temu tako, mora obstajati algoritem, ki olajša reševanje ogromnih sudokujev, optimizira globalne ladijske poti, razbije najsodobnejše šifriranje in avtomatizira dokaze matematičnih izrekov. Če je P ≠ NP, bodo številni računski problemi, ki so načeloma rešljivi, v praksi za vedno ostali nedosegljivi.

Raziskovalci so bili zaskrbljeni zaradi meja formalnega matematičnega sklepanja že dolgo preden je bil prvič artikuliran problem P proti NP - pravzaprav veliko pred začetkom sodobne računalniške znanosti. Leta 1921 je matematik David Hilbert, ko se je spopadal z istim vprašanjem, ki je skoraj stoletje pozneje pritegnilo Carmosinovo pozornost, predlagal raziskovalni program za utemeljitev matematike v absolutni gotovosti. Upal je, da bo izhajal iz nekaj preprostih predpostavk, imenovanih aksiomi, in izpeljal enotno matematično teorijo, ki bo izpolnjevala tri ključna merila.

Hilbertov prvi pogoj, doslednost, je bila bistvena zahteva, da je matematika brez protislovij: če bi bilo mogoče dokazati dve protislovni trditvi, izhajajoč iz istih aksiomov, bi bila celotna teorija nerešljiva. Toda teorija je lahko brez protislovij in še vedno omejena v svojem dosegu. To je bila motivacija za Hilbertov drugi pogoj, popolnost: zahteva, da so vse matematične izjave dokazljivo resnične ali dokazljivo napačne. Njegovo tretje merilo, odločljivost, je zahtevalo nedvoumen mehanski postopek za ugotavljanje, ali je katera koli matematična izjava resnična ali napačna. Na konferenci leta 1930 je Hilbert izjavil: »Naš slogan bo 'Vedeti moramo, vedeli bomo.'«

Samo leto pozneje je Gödel zadal prvi udarec Hilbertovim sanjam. On dokazano da bi samouničujočo izjavo, kot je "ta izjava je nedokazljiva", lahko izpeljali iz katerega koli ustreznega niza aksiomov. Če je taka izjava res nedokazljiva, je teorija nepopolna, če pa je dokazljiva, je teorija nedosledna - še slabši rezultat. V istem dokumentu je Gödel tudi dokazal, da nobena matematična teorija nikoli ne more dokazati lastne doslednosti.

Raziskovalci so še vedno upali, da se bo prihodnja teorija matematike, čeprav nujno nepopolna, vseeno izkazala za odločilno. Morda bi lahko razvili postopke, ki bi prepoznali vse dokazljive izjave, hkrati pa se izognili motečim predlogom, kot je Gödelov. Težava je bila v tem, da nihče ni vedel, kako razmišljati o teh hipotetičnih postopkih.

Nato je leta 1936 23-letni podiplomski študent po imenu Alan Turing preoblikoval Hilbertov pogoj odločljivosti v takrat neznanem jeziku računanja in mu zadal usoden udarec. Turing je oblikoval matematični model - zdaj znan kot Turingov stroj — ki bi lahko predstavljal vse možne algoritme in pokazal, da če bi Hilbertov postopek obstajal, bi ustrezal temu modelu. Nato je uporabil samoreferenčne metode, kot je Gödelova izkažejo obstoj neodločljivih izjav - ali, kar je enako, neizračunljivih problemov, ki jih noben algoritem ne bi mogel rešiti.

Hilbertov program je ležal v ruševinah: za vedno bodo obstajale temeljne omejitve glede tega, kaj je mogoče dokazati in kaj je mogoče izračunati. Toda ko so se računalniki razvili iz teoretičnih abstrakcij v resnične stroje, so raziskovalci spoznali, da je Turingovo preprosto razlikovanje med rešljivimi in nerešljivimi problemi pustilo veliko vprašanj neodgovorjenih.

Do šestdesetih let prejšnjega stoletja so računalniški znanstveniki razvili hitre algoritme za reševanje nekaterih problemov, medtem ko so bili za druge edini znani algoritmi neznosno počasni. Kaj pa, če vprašanje ne bi bilo le, ali so težave rešljive, ampak kako težko jih je rešiti?

"Pojavi se bogata teorija, odgovorov pa ne poznamo več," je dejal Carmosino.

Različne poti

Za ponazoritev, kako zapletena so lahko vprašanja o trdoti, razmislimo o paru tesno povezanih problemov, ki vključujejo grafe. To so mreže točk, imenovane vozlišča, povezane s črtami, imenovanimi robovi. Računalniški znanstveniki jih uporabljajo za modeliranje vsega kvantno računanje k pretok prometa.

Recimo, da vam je dan graf in vas prosimo, da poiščete nekaj, kar se imenuje Hamiltonova pot – pot, ki gre skozi vsako vozlišče točno enkrat. Ta problem je načeloma očitno rešljiv: obstaja le končno število možnih poti, tako da, če vse drugo odpove, lahko preprosto preverite vsako. To je v redu, če je vozlišč le nekaj, toda pri celo nekoliko večjih grafih število možnosti uide izpod nadzora, zaradi česar ta preprost algoritem hitro postane neuporaben.

Obstajajo bolj izpopolnjeni algoritmi Hamiltonove poti, ki se bolje borijo, vendar čas, ki ga algoritmi potrebujejo za rešitev problema, vedno eksponentno raste z velikostjo grafa. Ni treba, da so grafi zelo veliki, preden tudi najboljši raziskovalci algoritmov odkrijejo, da ne morejo najti poti »v razumnem času« Russell Impagliazzo, teoretik kompleksnosti na kalifornijski univerzi v San Diegu. »In z 'razumno količino časa' mislim 'preden se vesolje konča'.”

Problem Hamiltonove poti ima še eno zanimivo lastnost. Če nekdo trdi, da je našel Hamiltonovo pot na določenem grafu, lahko hitro preverite, ali je rešitev veljavna, tudi če je graf zelo velik. Vse, kar morate storiti, je, da sledite poti in odkljukate vozlišča enega za drugim ter preverite, ali niste nobenega vozlišča odkljukali dvakrat. Če na koncu ne manjka nobeno vozlišče, potem je pot Hamiltonova.

Čas, potreben za izvajanje tega algoritma za preverjanje rešitev, je sorazmeren z velikostjo grafa. To ga uvršča v širšo kategorijo polinomskih algoritmov, katerih časi delovanja naraščajo kot polinomske funkcije velikosti grafa. Polinomska rast je skromna v primerjavi z eksponentno rastjo, zato polinomski algoritmi ostanejo uspešni tudi na velikih grafih. "Je dramatično bolj učinkovito," je dejal Carmosino.

Problem Hamiltonove poti ima močno asimetrijo: pravilno rešitev lahko preverite s hitrim polinomskim algoritmom, vendar boste za iskanje rešitve potrebovali počasen eksponentni algoritem. Ta asimetrija se morda ne zdi presenetljiva - lažje je prepoznati umetniško mojstrovino kot jo ustvariti, lažje je preveriti matematični dokaz kot dokazati nov izrek - vendar nimajo vsi računski problemi tega asimetričnega značaja. Pravzaprav se problem, ki je zelo podoben iskanju Hamiltonovih poti, obnaša precej drugače.

Recimo, da ste ponovno dobili graf, zdaj pa morate poiskati "Eulerjevo pot", ki prečka vsak rob natanko enkrat. Spet je na voljo polinomski algoritem za preverjanje možnih rešitev, vendar tokrat obstaja tudi polinomski algoritem za rešitev problema. Tukaj ni asimetrije. V teoriji kompleksnosti se zdi, da je nekatere poti lažje najti kot druge.

Tako problem Hamiltonove poti kot problem Eulerjeve poti sta v kompleksnem razredu NP, ki je definiran tako, da vključuje vse probleme, katerih rešitve je mogoče preveriti s polinomskimi algoritmi. Tudi problem Eulerjeve poti spada v razred P, ker ga lahko reši polinomski algoritem, vendar kot kaže, to ne velja za problem Hamiltonove poti. Zakaj bi se ti dve grafični težavi, tako na videz podobni, tako dramatično razlikovali? To je bistvo problema P proti NP.

Univerzalno težko

Sprva so se razredi kompleksnosti zdeli kot priročne kategorije za razvrščanje problemov, ki so bili podobni, vendar niso neposredno povezani - nihče ni sumil, da ima iskanje Hamiltonovih poti kaj opraviti z drugimi težkimi računalniškimi problemi.

Leta 1971, v enem letu po preselitvi na Univerzo v Torontu, potem ko so mu zavrnili službo v Združenih državah, je teoretik kompleksnosti Stephen Cook objavil izjemen rezultat. Določen problem NP je identificiral s čudno lastnostjo: če obstaja polinomski algoritem, ki lahko reši ta problem, lahko reši tudi vse druge probleme v NP. Zdelo se je, da je Cookov "univerzalni" problem samoten stolpec, ki podpira razred navidez težkih problemov in jih ločuje od spodnjih preprostih problemov. Razbijte to eno težavo in ostali NP se bodo zrušili.

Cook je posumil, da ni hitrega algoritma za njegovo univerzalno težavo, in je to povedal sredi prispevka ter dodal: "Menim, da je vredno vložiti precej truda, da bi dokazali to domnevo." Izkazalo se je, da je "precejšen trud" podcenjen.

Približno v istem času je podiplomski študent v Sovjetski zvezi imenovan Leonid Levin dokazal a podoben rezultat, le da je identificiral več različnih univerzalnih problemov. Poleg tega ameriški teoretik kompleksnosti Richard Karp dokazano da je lastnost univerzalnosti, ki sta jo identificirala Cook (in Levin, čeprav sta Karp in Cook za Levinovo delo vedela šele leta pozneje), sama skoraj univerzalna. Skoraj vsak problem NP brez znanega polinomskega algoritma - to je skoraj vsak zlahka preverljiv problem, ki se je zdel težak - je imel enako lastnost, ki je postala znana kot popolnost NP.

To pomeni vse NP-popolne probleme – problem Hamiltonove poti, sudoku in tisoče drugih — so v natančnem smislu enakovredni. "Imate vse te različne naravne naloge in vse se čarobno izkažejo za isto nalogo," je dejal Ilango. "In še vedno ne vemo, ali je ista naloga možna ali ne."

Rešitev težavnosti katerega koli NP-popolnega problema bi zadostovala za rešitev vprašanja P proti NP. Če je P ≠ NP, razlikovanje med lahkimi in težkimi problemi zadržuje na tisoče stolpcev, ki so vsi enako močni. Če je P = NP, je celotna zgradba na robu propada in samo čaka, da pade en sam kos.

Cook, Levin in Karp so združili nekaj, kar se je zdelo kot veliko nepovezanih problemov. Zdaj so morali teoretiki kompleksnosti samo rešiti eno težavo: ali je P = NP ali ne?

Petdeset let kasneje vprašanje ostaja neodgovorjeno. Kabanets je sklepanje o mejah računanja primerjal z raziskovanjem velikega ozemlja brez občutka za celotno sliko. Bitje z neomejeno računsko močjo bi lahko pokukalo z vrha gore in zajelo celotno pokrajino naenkrat, a navadni smrtniki ne morejo računati na takšno prednost. "Tisti med nami, ki smo na dnu gore, lahko poskusimo morda skočiti gor in dol za boljši pogled," je dejal.

Recimo, da je P = NP. Da bi to dokazali, bi morali raziskovalci najti hiter algoritem za NP-popoln problem, ki se morda skriva v nekem nejasnem kotičku te ogromne pokrajine. Ni zagotovila, da ga bodo kmalu našli: teoretiki zapletenosti so občasno odkril genialni algoritmi za na videz težke (čeprav ne NP-popolne) probleme šele po desetletjih dela.

Zdaj predpostavimo, da je P ≠ NP. To se zdi še težje dokazati. Teoretiki kompleksnosti bi morali ugotoviti, da ne more obstajati hiter algoritem, ki bi učinkovito predvideval in preprečil najboljša prizadevanja vseh bodočih raziskovalcev.

Del težave je, da ne veste, kje začeti. Vendar ni tako, da raziskovalci tega niso poskusili. Skozi desetletja so problem napadli z različnih zornih kotov in ugotovili, da je pot blokirana na vsakem koraku. "To je ena najbolj očitnih resnic v teoretični računalniški znanosti," je dejal Carmosino. "Ko imate pojav, ki je tako trajen, želite nekaj razlage."

Do zadnjega letnika kolidža ga je Carmosino radovednost pripeljala od Gödela do podiplomskega tečaja teorije kompleksnosti. Bil je presenečen, ko je ugotovil, da porabi več časa za domače naloge kot za svoj strastni projekt, računalniški program, ki bi se naučil pripovedne strukture pravljic in ustvaril nove.

"Pomislil sem, 'Vau, to moram vzeti resno,'" se je spominjal Carmosino. Kmalu ga je predmet tako zavzel, da mu je mentor nežno predlagal, naj ponovno razmisli o svojih načrtih po diplomi.

»Rekel je: 'Veš, če hočeš nadaljevati s tem, če se želiš še naprej ukvarjati s teoretično računalniško znanostjo in teorijo kompleksnosti, lahko: Temu se reče podiplomska šola,'« je dejal Carmosino. Po pridobitvi magisterija se je leta 2012 preselil v San Diego, da bi delal v smeri doktorata pod nadzorom Impagliazza.

Carmosinov glavni cilj je bil sprva bolje razumeti a mejnik papirja izpred dveh desetletij, ki je prevzela njegovo domišljijo. Ta članek teoretikov kompleksnosti Aleksander Razborov in Steven Rudich, je pokazal, da bi določena "naravna" strategija za dokazovanje P ≠ NP skoraj zagotovo spodletela, ker bi uspeh imel visoko ceno - popolno zlom kriptografije - kar so raziskovalci ocenili kot zelo malo verjetno. Raziskovalci so rezultat Razborova in Rudicha interpretirali kot oviro za ta priljubljen pristop k dokazovanju P ≠ NP.

Ta »naravna dokazna ovira« je samo ena od mnogih znanih ovir za reševanje odprtih problemov v teoriji kompleksnosti. Vsaka deluje kot cestna zapora in opozarja, da je na videz obetavna pot pravzaprav slepa ulica. Skupaj te ovire kažejo, da bi moral biti vsak dokaz, ki rešuje problem P proti NP, radikalno drugačen od česar koli, kar se je uporabljalo v preteklosti; zato večina raziskovalcev meni, da je rešitev še daleč. Toda vsaj ovire jim povedo, kam naj ne iščejo.

"Teorija kompleksnosti je prekleta in blagoslovljena s toliko ovirami," je dejal Ilango.

Ko je Carmosino naletel na naravno dokazno oviro, je bil star že skoraj 20 let. Vendar je sumil, da ima več lekcij za raziskovalce. Ta občutek bo nekega dne potrjen, ko bo s tremi kolegi dokazal presenetljiv rezultat s preučevanjem naravne dokazne ovire z vidika metakompleksnosti. Njihov dokaz je bil eden redkih večjih rezultatov, ki so sprožili novo zanimanje za metakompleksnost, kar je v zadnjih nekaj letih privedlo do hitrega napredka.

Toda da bi sledili poti od naravne dokazne ovire do metakompleksnosti, se bomo morali vrniti tja, kjer smo pustili raziskovalce v sedemdesetih letih prejšnjega stoletja, ko so se prvič začeli ukvarjati s problemom P proti NP. Zakaj je bilo tako težko dokazati težave?

Krožna pot

Sprva so raziskovalci poskušali dokazati P ≠ NP - to je dokazati, da nekaterih problemov NP ni mogoče rešiti z nobenim možnim polinomskim algoritmom - z uporabo različic tehnik, ki jih je Turing uporabil za dokazovanje, da nekaterih problemov ni mogoče rešiti z nobenim algoritmom. . Ampak oni hitro odkril dokaz, da te metode ne bi delovale - prva večja ovira pri reševanju vprašanja P proti NP. Zato so začeli iskati drug pristop in kmalu so ga našli v delu Turingovega sodobnika Claude Shannon.

Shannon, ki je odraščala v majhnem mestecu v severnem Michiganu, se je zdela malo verjetna oseba, ki bi začela informacijsko dobo. Kljub temu je ponazarjal interdisciplinarno naravo nastajajoče discipline računalništva, saj se je enako dobro počutil v elektrotehniki in matematični logiki. V njegovem magistrsko delo, je Shannon pokazal, kako lahko vezja iz elektromehanskih stikal predstavljajo logične izraze, ki vključujejo logične spremenljivke – količine, ki lahko prevzamejo samo dve vrednosti (kot sta true ali false ali 1 in 0).

V teh izrazih so logične spremenljivke povezane z »logičnimi vrati« IN, ALI in NE. Elementarna izraza A IN B je na primer resničen, če sta oba A in B resnična, drugače pa napačen; A ALI B je po drugi strani resničen, če je resnična vsaj ena od obeh spremenljivk. Vrata NOT so še enostavnejša: obrnejo vrednost ene same spremenljivke. Z dovolj teh osnovnih gradnikov lahko izvedete kakršen koli izračun.

»Ko na koncu dneva pogledate svoj računalnik, kaj počne? Teče krog,« je rekel Ilango.

Shannonovo delo je teoretikom predlagalo nov način razmišljanja o težavnosti računalniških problemov, ki se imenuje "kompleksnost vezij", čeprav so zadevna vezja le matematične abstrakcije. Nekaj ​​časa so raziskovalci mislili, da bi ta pristop lahko bil način za razrešitev P proti NP, vendar je sčasoma sled naletela na naravno dokazno oviro.

Okvir kompleksnosti vezja zahteva ponoven razmislek o najosnovnejših konceptih v Turingovem modelu računanja. Tukaj raziskovalci namesto računalniških problemov in algoritmov, ki jih rešujejo, upoštevajo logične funkcije in vezja, ki jih izračunajo. Logična funkcija sprejme logične spremenljivke - resnice in neresničnosti, 1s in 0s - in izpiše bodisi true ali false, 1 ali 0. Tako kot algoritem tudi vezje opisuje postopek za ustvarjanje izhoda glede na kateri koli vnos.

"Kot razumem, so se ljudje začeli ukvarjati s kompleksnostjo vezja, ker so se odločili, da so Turingovi stroji preveč zapleteni," je dejal Ryan Williams, teoretik kompleksnosti na MIT. "Vezja lahko preučujemo od vrat do vrat."

Tako kot lahko obstaja veliko algoritmov za reševanje katerega koli danega računalniškega problema, nekateri hitrejši od drugih, lahko veliko različnih vezij izračuna katero koli logično funkcijo, nekatera z manj vrati kot druga. Raziskovalci definirajo kompleksnost vezja funkcije kot skupno število vrat v najmanjšem vezju, ki jo izračuna. Za funkcijo s fiksnim številom vhodnih spremenljivk je tudi kompleksnost vezja fiksna številka - pri nekaterih funkcijah višja kot pri drugih.

Toda v mnogih primerih lahko razmislite o bolj zapletenih različicah iste funkcije s povečanjem števila vhodnih spremenljivk, tako kot lahko otežite problem Hamiltonove poti z upoštevanjem večjih grafov. Raziskovalci nato razmislijo o istem vprašanju, kot ga zastavijo, ko preučujejo čase izvajanja algoritmov: Ali najmanjše število vrat, potrebnih za izračun logične funkcije, raste polinomsko ali eksponentno, ko se povečuje število vhodnih spremenljivk? Raziskovalci ti dve kategoriji funkcij imenujejo "enostavne za izračunavanje" oziroma "težke za izračunavanje".

Logična funkcija, ki jo je enostavno izračunati, je podobna računskemu problemu v razredu P, ki ga je mogoče rešiti z algoritmom, ki se izvaja v polinomskem času. Obstajajo pa tudi funkcije, ki so analogne trdim problemom NP, kjer najboljši način, ki so ga odkrili raziskovalci, za izračun postopno večjih različic zahteva eksponentno naraščajoče število vrat, vendar je odgovor mogoče enostavno preveriti. Če bi teoretiki kompleksnosti lahko dokazali, da res ni boljšega načina za izračun takšne funkcije, bi to pomenilo P ≠ NP.

To je bila strategija, ki jo je v osemdesetih letih zasledovala večina teoretikov kompleksnosti. In možnosti so bile na njihovi strani. Shannon je imela dokazano leta 1949, da ima skoraj vsaka logična tabela resnic (ki je samo dolg seznam vseh možnih vhodov in izhodov logične funkcije fiksne velikosti) kompleksnost vezja, ki je praktično kar se da visoka. Uporabil je osupljivo preprost argument: Obstaja veliko manj načinov za kombiniranje majhnega števila vrat kot načinov za kombiniranje številnih vrat.

"Preprosto ni dovolj majhnih tokokrogov," je dejal Aaronson.

Tako so se teoretiki kompleksnosti znašli v čudni situaciji. Če ima skoraj vsaka tabela resnic visoko kompleksno vezje, potem mora biti skoraj vsako logično funkcijo težko izračunati. Raziskovalci so morali identificirati eno samo tako funkcijo, za katero je bilo znano, da je tudi v razredu NP. Kako težko bi to lahko bilo?

Crypto Bros

Sprva je bil napredek hiter. Leta 1981 Sipser in dva sodelavca dokazano da je bilo določeno Boolovo funkcijo vsekakor težko izračunati, če so uporabili vezja z določenimi omejitvami glede razporeditve vrat.

»Fantazija je bila, da boste lahko dokazali stvari o teh omejenih modelih in nato gradili na tem, kar ste se naučili, da boste delali z vedno manj omejitvami,« je dejal Sipser.

Leta 1985 je Razborov naredil naslednji velik korak. Pravkar je začel podiplomski študij v Moskvi in ​​se je po naključju pridružil prizadevanjem, ko se je loteval problema v drugi veji matematike, kjer se je izkazalo, da je rešitev problema P proti NP predpogoj.

"Imel sem preprosto srečo, da nisem vedel, kako težak je ta problem," je dejal Razborov. "Drugače morda sploh ne bi začel."

Razborov je analiziral vezja, ki vsebujejo le vrata IN in ALI, in dokazano da je bilo določeno funkcijo težko izračunati z uporabo takih vezij, ne glede na to, kako so bila vrata razporejena - še več, znano je, da je ta funkcija NP-popolna. Vse, kar so raziskovalci morali storiti, da bi razrešili P proti NP, je bilo razširiti Razborovljeve tehnike na vezja z NE vrati.

"Bil je nekakšen univerzalni občutek, da še en korak, še ena stavka in bomo to dobili," je dejal Razborov. Ampak to se ni zgodilo. Razborov je sam dokazal, da njegova metoda ne bi uspela, če mešanici NE bi dodali vrat, in nihče ne bi mogel najti druge poti naprej. Ko so leta minila, se je začel spraševati, zakaj je sled zamrla.

Rudich je v Združenih državah razmišljal o istem vprašanju. Z Impagliazzo sta bila sošolca na fakulteti, ki sta skupaj nadaljevala podiplomski študij. Njuno prijateljstvo je sprožilo skupno navdušenje nad Gödelovimi in Turingovimi samoreferenčnimi dokazi in njihovimi posledicami za temelje matematike in računalništva.

"Naša šala je bila, da bomo dobili gumb z napisom 'samoreferenca'," je dejal Impagliazzo.

Rudich in Impagliazzo sta kot podiplomska študenta delala na teoretičnih temeljih kriptografije zapletenosti, temi, ki ponuja morda najboljšo praktično motivacijo za poskus dokazovanja P ≠ NP. Kriptografi skrijejo tajna sporočila tako, da jih zakrijejo v "psevdonaključnost" - sporočilo, šifrirano na ta način, bo vsakemu prisluškovalcu videti kot naključna zmešnjava številk, vendar ga nameravani prejemnik še vedno lahko dekodira. Toda kako ste lahko prepričani, da bo morebitnemu prisluškovalcu pretežko razbiti kodo?

Tu nastopi teorija kompleksnosti. Metode šifriranja, ki se danes najpogosteje uporabljajo, vse temeljijo na navidezno težkih težavah NP – za dešifriranje sporočila bi napadalec potreboval še neodkrit hiter algoritem za rešitev težave. Če želite ugotoviti, ali so te metode resnično varne, morate dokazati, da je P ≠ NP. Sipser je dejal, da lahko brez dokaza vse, kar lahko storite, "upate, da tisti, pred katerim poskušate obdržati skrivnost, ni boljši matematik od vas."

Čeprav je bila sama po sebi fascinantna, se je zdela kriptografija daleč stran od samoreferenčnih argumentov, ki so najprej pritegnili Rudicha in Impagliazza na to področje. Toda ko se je Rudich trudil razumeti, zakaj je pristop kompleksnosti vezja zastal, se je začel zavedati, da subjekta vendarle nista tako daleč narazen. Strategija, ki so jo sprejeli raziskovalci v svojih poskusih, da bi dokazali, da ima P ≠ NP samouničujoč značaj, ki spominja na znamenito Gödelovo izjavo "ta izjava je nedokazljiva" - in kriptografija bi lahko pomagala razložiti, zakaj. V Rusiji je Razborov približno v istem času odkril podobno povezavo. To so bila semena naravne dokazne ovire.

Napetost v središču naravne dokazne ovire je, da je naloga razlikovanja visokokompleksnih funkcij od nizkokompleksnih podobna nalogi razlikovanja prave naključnosti od psevdonaključnosti, ki se uporablja za šifriranje sporočil. Radi bi pokazali, da se visokokompleksne funkcije kategorično razlikujejo od nizkokompleksnih funkcij, da bi dokazali P ≠ NP. Želeli pa bi tudi, da se psevdonaključnost ne razlikuje od naključnosti, da bi bili prepričani v varnost kriptografije. Mogoče ne moremo imeti obojega.

Kruta šala

Leta 1994 sta Razborov in Rudich ugotovila, da sta naletela na podobna spoznanja, in začela sta sodelovati, da bi združila svoje rezultate. Najprej so opazili, da so vsi prejšnji poskusi dokazati P ≠ NP z uporabo kompleksnosti vezja sprejeli isto splošno strategijo: Identificirajte posebno lastnost NP-popolne logične funkcije, nato pa dokažite, da nobena funkcija, ki jo je enostavno izračunati, ne more deliti te lastnosti. To bi pokazalo, da je bilo izbrano NP-popolno funkcijo resnično težko izračunati, kar dokazuje, da je P ≠ NP.

Sipser, Razborov in drugi so to isto strategijo uspešno uporabili za dokazovanje svojih bolj omejenih rezultatov in v vsakem primeru je bila posebna lastnost, ki so jo ugotovili raziskovalci, skupna večini Boolovih funkcij. Razborov in Rudich sta skovala izraz »naravni dokaz« za ta primer, ko je bila lastnina široko razdeljena, preprosto zato, ker ni bilo znane druge možnosti. Če bi bili "nenaravni" dokazi možni, bi morali biti zelo protislovni in bi si zaslužili to ime.

Razborov in Rudich sta nato dokazala svoj glavni rezultat: naraven dokaz P ≠ NP bi zahteval zelo celovito razumevanje, kako se razlikujejo enostavne in težko izračunljive funkcije, to znanje pa bi lahko spodbudilo tudi hiter algoritem za enostavno odkrivanje -to-compute funkcije, tudi če so na videz zapletene. Če bi teoretiki kompleksnosti uspeli z naravnim dokazom P ≠ NP, bi odkrili skoraj nezmotljiv način, da pogledajo poljubno tabelo resnic in ugotovijo, ali ima ustrezna funkcija visoko ali nizko kompleksnost vezja - veliko močnejši in bolj splošen rezultat kot so se odločili dokazati.

"Skoraj si ne morete pomagati, da ne bi dobili več, kot ste pričakovali," je dejal Carmosino.

To je tako, kot če bi poskušali preveriti dejstvo določene izjave, vendar se je vsak poskus spremenil v načrt za detektor laži za splošno uporabo - zdelo bi se prelepo, da bi bilo res. Za teoretike kompleksnosti se je zaradi presenetljive moči naravnih dokazov uspeh prav tako zdel manj verjeten. A če bi takšen dokaz uspel, bi bile nepričakovane posledice slaba novica za kriptografijo zaradi povezave med kompleksnostjo vezja in psevdonaključnostjo.

Da bi razumeli to povezavo, si predstavljajte, da pogledate izhodni stolpec v tabeli resnic logične funkcije z veliko vhodnimi spremenljivkami in zamenjate vsako »true« z 1 in vsako »false« z 0:

Če ima logična funkcija visoko zapletenost vezja, tega dolgega seznama izhodov načeloma ne bo mogoče ločiti od resnično naključnega niza 0 in 1 - tistega, ki ga dobimo z večkratnim metanjem kovanca, na primer. Če pa ima funkcija nizko zapletenost vezja, mora imeti niz preprost, jedrnat opis, tudi če je videti zapleten. Zaradi tega je zelo podoben psevdonaključnim nizom, ki se uporabljajo v kriptografiji, katerih jedrnat opis je skrivno sporočilo, zakopano v tej navidezni naključnosti.

Rezultat Razborova in Rudicha je torej pokazal, da bi vsak naravni dokaz P ≠ NP dal tudi hiter algoritem, ki bi lahko razlikoval psevdonaključne nize, ki vsebujejo skrita sporočila, od resnično naključnih. Varna kriptografija bi bila nemogoča - ravno nasprotno od tega, kar so raziskovalci upali ugotoviti z dokazovanjem P ≠ NP.

Po drugi strani pa, če je možna varna kriptografija, potem naravni dokazi niso izvedljiva strategija za dokazovanje P ≠ NP – predpogoj za varno kriptografijo. To je na kratko naravna dokazna ovira. Zdelo se je, kot da so teoretiki kompleksnosti deležni krute šale.

"Če verjamete v trdoto, potem morate verjeti, da je trdoto težko dokazati," je dejal Kabanets.

V Metaverse

Ta povezava med posledicami domneve P ≠ NP in težavo dokazovanja je bila zanimiva, vendar jo je bilo težko določiti. Prvič, naravna dokazna ovira je blokirala le en pristop k dokazovanju P ≠ NP. Po drugi strani pa težave pri dokazovanju P ≠ NP ni povezal s samim P ≠ NP, temveč z obstojem varne kriptografije – tesno povezan, a ne povsem enakovreden problem. Da bi resnično razumeli povezavo, bi se raziskovalci morali udobiti z metakompleksnostjo.

"Obstaja ta intuicija, da 'oh, ker je P ≠ NP, je težko dokazati, da je P ≠ NP,'" je dejal Williams. "Toda da bi celo razumeli to intuicijo, morate začeti razmišljati o nalogi dokazovanja nečesa, kot je P ≠ NP, kot računalniški problem."

To je Kabanets naredil kot podiplomski študent. Odraščal je v Ukrajini, dve leti po razpadu Sovjetske zveze pa je končal dodiplomski študij računalništva. V pretresih, ki so sledili, je imel malo priložnosti, da bi se ukvarjal s teoretičnimi temami, ki so ga najbolj zanimale.

"Želel sem narediti nekaj bolj akademskega," se je spominjal Kabanets. "Pa tudi radoveden sem bil videti svet." V Kanado se je preselil zaradi podiplomskega študija in tam je izvedel za naravno dokazno oviro. Tako kot Carmosino je bil tudi Kabanets navdušen nad rezultatom. "Zdelo se je zelo globoko, da imate to povezavo," je dejal.

Leta 2000, proti koncu svojega podiplomskega študija, je ugotovil, da se v njegovih pogovorih z Jin-Yi Cai, teoretik kompleksnosti, ki je bil takrat na dopustu v Torontu. Na oviro niso začeli gledati kot na oviro, ampak kot na povabilo – priložnost, da natančno raziščejo, kako težko je dokazati težave. The papirja v katerem so postavili to novo perspektivo, bi postalo eno najvplivnejših zgodnjih del na nastajajočem področju metakompleksnosti.

Prispevek Kabanetsa in Caija je izpostavil računalniški problem, ki je impliciran v formulaciji naravne dokazne ovire Razborova in Rudicha: glede na resničnostno tabelo logične funkcije določite, ali ima visoko ali nizko kompleksnost vezja. To so poimenovali problem najmanjše velikosti vezja ali MCSP.

MCSP je najpomembnejši metakompleksni problem: računski problem, katerega predmet ni teorija grafov ali druga zunanja tema, ampak sama teorija kompleksnosti. Dejansko je to kot kvantitativna različica vprašanja, ki je gnalo teoretike kompleksnosti, da so se lotili P proti NP z uporabo pristopa kompleksnosti vezja v osemdesetih letih prejšnjega stoletja: Katere Boolove funkcije je težko izračunati in katere enostavno?

"Če bi prišli do algoritma MCSP, bi bil to kot način avtomatizacije tega, kar počnemo v teoriji kompleksnosti," je dejal Impagliazzo. "Moral bi nam dati vsaj izjemen vpogled v to, kako lahko svoje delo opravljamo bolje."

Teoretikov zapletenosti ne skrbi, da bi jih ta čarobni algoritem pustil brez dela - mislijo, da sploh ne obstaja, ker sta Razborov in Rudich pokazala, da bi vsak tak algoritem za razlikovanje visoko zapletenih tabel resnice od nizko zapletenih naredil kriptografijo nemogoče. To pomeni, da je MCSP verjetno težka računska težava. Toda kako težko je? Ali je NP-popoln, kot problem Hamiltonove poti in skoraj vsak drug problem, s katerim so se raziskovalci spopadali v šestdesetih letih?

Za težave v NP, "kako težko je?" je običajno dovolj enostavno odgovoriti, vendar se je zdelo, da je MCSP nenavaden izstop. »Imamo zelo malo 'lebdečih' problemov, ki niso bili povezani s tem otokom težav s popolnostjo NP, čeprav se zdijo težki,« je dejal Kabanets.

Kabanets je vedel, da on in Cai nista prva, ki sta razmišljala o problemu, ki so ga poimenovali MCSP. Sovjetski matematiki so preučevali zelo podoben problem v začetku petdesetih let prejšnjega stoletja, ko so poskušali razumeti notranjo težavnost različnih računalniških problemov. Leonid Levin se je boril s tem, ko je v poznih šestdesetih letih prejšnjega stoletja razvijal to, kar je postalo teorija NP-popolnosti, vendar ni mogel dokazati, da je NP-popolna, in je objavil svoj temeljni članek brez nje.

Po tem je problem 30 let pritegnil malo pozornosti, dokler Kabanets in Cai nista opazila njegove povezave z naravno dokazno pregrado. Kabanets ni pričakoval, da bo sam rešil vprašanje - namesto tega je želel raziskati, zakaj je bilo tako težko dokazati, da je ta na videz težka težava glede računalniške trdote dejansko težka.

"To je v nekem smislu meta-meta-kompleksnost," je rekel Rahul Santhanam, teoretik kompleksnosti na Univerzi v Oxfordu.

Toda ali je šlo za trdoto do konca ali je obstajal vsaj način za razumevanje, zakaj raziskovalcem ni uspelo dokazati, da je MCSP NP-popoln? Kabanets je odkril, da, da, obstaja razlog: Težavnost razumevanja kompleksnosti vezja deluje kot ovira za katero koli znano strategijo za dokazovanje NP-popolnosti MCSP – težava, ki se sama nanaša na težavnost razumevanja kompleksnosti vezja. Izkrivljena, samouničujoča logika naravne dokazne ovire se je zdela neizogibna.

Možno je tudi, da MCSP ni NP-popoln, vendar se tudi to zdi malo verjetno - nekatere enostavnejše različice problema so že znane kot NP-popolne.

"Enostavno nimamo lepega mesta, kjer bi ga postavili, ki bi ga neposredno povezal z vsemi drugimi problemi, ki jih preučujemo," je dejal Impagliazzo.

Kabanets je osvetlil nenavadno vedenje MCSP, vendar ni vedel, kako narediti nadaljnji napredek. Raziskave metakompleksnosti so se upočasnile. Ponovno se bo razmahnilo 16 let pozneje, ko so raziskovalci odkrili presenetljivo povezavo z drugim temeljnim vprašanjem: kako težko je reševati probleme, če večino časa skrbite samo za pravilen odgovor?

War of the Worlds

Za vsakodnevne težave so odgovori, ki večino časa delujejo, pogosto dovolj dobri. Svoje vožnje načrtujemo za tipične prometne vzorce, na primer, ne za najslabše možne scenarije.

Večino teoretikov kompleksnosti je težje zadovoljiti: Zadovoljni so le s tem, da problem razglasijo za lahkega, če lahko najdejo hiter algoritem, ki dobi pravi odgovor na vsak možen vnos. Ta standardni pristop razvršča probleme glede na to, kar raziskovalci imenujejo zapletenost v "najslabšem primeru". Obstaja pa tudi teorija zapletenosti »povprečnega primera«, po kateri se težave štejejo za lahke, če obstaja hiter algoritem, ki dobi pravi odgovor na večino vnosov.

Razlikovanje je pomembno za kriptografe. Predstavljajte si računski problem, ki ga je enostavno rešiti za skoraj vsak vnos, razen v nekaj trdovratnih primerih, ko najboljši algoritem odpove. Teorija zapletenosti v najslabšem primeru meni, da je to težka težava, vendar je za kriptografijo neuporabna: Če je le nekatera vaša sporočila težko dešifrirati, kaj je smisel?

Pravzaprav je bil Levin tisti, ki je desetletje po njegovem pionirskem delu o NP-popolnosti začel s strogo študijo kompleksnosti povprečnih primerov. V vmesnih letih je naletel na sovjetske oblasti - bil je nespoštljiv povzročitelj težav, ki je občasno spodkopaval domoljubne dejavnosti v svoji mladinski skupini komunistične partije. Leta 1972 mu je bil zavrnjen doktorat iz izrazito političnih razlogov.

»Da bi bil v Sovjetski zvezi uspešen kot mlad raziskovalec, nisi mogel biti zelo samozavesten in težko si je predstavljati, da Leonid ne bi bil samozavesten,« je dejal Impagliazzo.

Levin je leta 1978 emigriral v ZDA, sredi osemdesetih pa se je posvetil kompleksnosti povprečnih primerov. Začel je sodelovati z drugimi pri nadaljnjem razvoju teorije, vključno z Impagliazzom, takratnim podiplomskim študentom. Toda tudi ko so napredovali, je Impagliazzo ugotovil, da so raziskovalci pogosto govorili drug mimo drugega. Vse je želel spraviti na isto stran in ni pomagalo, da so bili Levinovi članki slavno jedrnati – tisti, ki začel polje povprečno zahtevnega primera je bil dolg manj kot dve strani.

»Nameraval sem prevesti Leonidovo delo v bolj dostopne tehnične izraze,« je dejal Impagliazzo. Odločil se je, da začne s kratkim, igrivim pregledom velike slike, preden se potopi v matematiko. "To je nekako prevzelo časopis in to je tako ali tako edini del, ki se ga kdo spomni."

O papirja, ki je izšla leta 1995, je takoj postala klasika. Impagliazzo je skoval muhasta imena za petih svetov odlikujejo različne stopnje računalniške trdote in različne kriptografske zmogljivosti. Živimo v enem od teh svetov, a ne vemo v katerem.

Odkar se je pojavil Impagliazzov članek, so raziskovalci sanjali o odstranitvi delov njegovega miniaturnega multiverzuma – zožanju prostora možnosti z dokazovanjem, da nekateri svetovi vendarle niso mogoči. Dva svetova sta še posebej mamljiva tarča: tista, kjer je kriptografija nemogoča, čeprav je P ≠ NP.

V enem od teh svetov, imenovanem Heuristica, je vse NP-popolne probleme enostavno rešiti na večini vhodov, vendar hitri algoritmi občasno delajo napake, zato se ti problemi še vedno štejejo za težke po standardih teorije kompleksnosti v najslabšem primeru. To je svet, v katerem je kriptografija nemogoča, saj je skoraj vsako kodo zlahka vdreti. V drugem svetu, imenovanem Pessiland, je kriptografija nemogoča iz drugega razloga: vsaka težava je težka v smislu povprečnega primera, toda šifriranje sporočila naredi nečitljivo celo za tistega, ki mu je namenjen.

Izkazalo se je, da sta ta dva svetova tesno povezana s problemi metakompleksnosti - zlasti je usoda Heuristica povezana z dolgotrajnim vprašanjem, ali je MCSP NP-popoln. Vprašanje, ki je tako dolgo nazaj fasciniralo Kabanetsa in begalo Levina, ni zgolj radovednost: na kocki je cel svet.

Da bi izključili Heuristica, bi morali raziskovalci zrušiti razliko med kompleksnostjo najslabšega in povprečnega primera – to pomeni, da bi morali dokazati, da lahko kateri koli hipotetični algoritem, ki pravilno reši NP-popoln problem na večini vhodnih podatkov, dejansko reši v vseh primerih. Znano je, da tovrstna povezava, imenovana zmanjšanje najslabšega do povprečnega primera, obstaja za določene težave, vendar nobena od njih ni NP-popolna, zato ti rezultati ne pomenijo ničesar bolj splošnega. Odprava Heuristica bi kriptografe popeljala na pol poti do uresničitve sanj o varnem šifriranju na podlagi ene same predpostavke, da je P ≠ NP.

Toda uničenje sveta ni majhen podvig. Leta 2003 dva teoretika kompleksnosti je pokazala, da bi obstoječi pristopi k dokazovanju redukcij od najslabšega do povprečnega primera za znane NP-popolne probleme pomenili nenavadne posledice, kar kaže na to, da taki dokazi verjetno niso mogoči.

Raziskovalci bi morali najti drug pristop in zdaj mislijo, da je MCSP morda le težava, ki jo potrebujejo. Toda to ni postalo jasno več kot desetletje. Prvi vpogled v povezavo se je pojavil iz vztrajne fascinacije Marca Carmosina nad naravno dokazno pregrado.

Carmosino se je z raziskavo metakompleksnosti prvič srečal kot podiplomski študent preko a Papir 2013 Kabanets in štirje drugi raziskovalci, ki so nadalje razvili pristop k naravni dokazni pregradi, ki ga je Kabanets uvedel več kot desetletje prej. To je samo utrdilo njegovo prepričanje, da se je dalo še več naučiti iz klasičnega prispevka Razborova in Rudicha.

"Takrat sem bil obseden s tem papirjem," je dejal Carmosino. "Nič se ni spremenilo."

Obsedenost je končno obrodila sadove med obiskom semestralne delavnice na kalifornijski univerzi Berkeley, kjer je večino časa preživel v pogovorih z Impagliazzom, Kabanetsom in Antonina Kolokolova, teoretik kompleksnosti na Univerzi Memorial v Novi Fundlandiji, ki je sodeloval s Kabanetsom pri dokumentu iz leta 2013. Carmosino je z njimi že enkrat sodeloval in to uspešno sodelovanje mu je vlilo samozavest, da jih je zasul z vprašanji o temi, ki ga je najbolj navdušila.

"Ljudem je delal motnje na dober način," se je spominjal Kabanets.

Sprva je imel Carmosino nove ideje za dokazovanje NP-popolnosti za različico MCSP, ki se je pojavila v dokumentu Razborova in Rudicha o naravni dokazni pregradi. Toda te zamisli se niso uresničile. Namesto tega je Impagliazzova nenavadna pripomba spodbudila štiri raziskovalce, da so ugotovili, da lahko naravna dokazna pregrada ustvari zmogljivejše algoritme, kot si je kdorkoli mislil – v cestno zaporo je bil vgraviran skrivni zemljevid.

V Papir 2016, so štirje raziskovalci dokazali, da bi lahko določeno vrsto algoritma MCSP v povprečnem primeru uporabili za izdelavo najslabšega algoritma za prepoznavanje vzorcev, skritih v naključnih nizih števk - naloga, ki jo računalniški znanstveniki imenujejo "učenje". To je osupljiv rezultat, ker se intuitivno učenje zdi težje kot naloga binarnega razvrščanja – visoka ali nizka zapletenost –, ki jo izvaja algoritem MCSP. In presenetljivo je povezal najslabšo zapletenost ene naloge s povprečno zapletenostjo druge.

"Ni bilo očitno, da bi taka povezava sploh obstajala," je dejal Impagliazzo.

Hiter algoritem za MCSP je povsem hipotetičen za splošna logična vezja: ne more obstajati, razen če se izkaže, da je MCSP lahek računski problem, kljub vsem dokazom o nasprotnem, kar pomeni, da je učni algoritem, ki ga nakazuje dokument štirih raziskovalcev, enako hipotetično.

Toda za nekatere enostavnejše različice MCSP - razlikovanje visoko zapletenih tabel resnice od nizko zapletenih, ko obstajajo posebne omejitve za vezja - so hitri algoritmi znani že vrsto let. Članek Carmosino, Impagliazzo, Kabanets in Kolokolova je pokazal, da je te algoritme mogoče preoblikovati v učne algoritme, ki so bili prav tako omejeni, vendar še vedno močnejši od vseh, ki so jih raziskovalci prej razumeli na tako strogi teoretični ravni.

"Nekako njihov samoreferenčni okus vam omogoča, da delate stvari, ki jih na videz ne morete narediti z bolj standardnimi težavami," je dejal Ilango.

Rezultat je pritegnil pozornost teoretikov kompleksnosti, ki so se ukvarjali z drugimi temami. To je bil tudi predogled nadaljnjih povezav med metakompleksnostjo in kompleksnostjo povprečnih primerov, ki se bodo pojavile v prihodnjih letih.

Predvsem pa je bil dokaz, kako daleč lahko pridejo raziskovalci s preprostimi vprašanji o ovirah, za katere se sprva zdi, da le ovirajo njihov napredek.

"Ta vrsta dvojnosti je tema vsaj zadnjih 30 ali 40 let kompleksnosti," je dejal Impagliazzo. "Ovire so pogosto priložnosti."

Delni kredit

Napredek se je le pospešil v letih, odkar so Carmosino in njegovi kolegi objavili svoj članek.

"Dogajajo se nove stvari," je dejala Kolokolova. "Obstaja veliko zelo, zelo bistrih mladih raziskovalcev."

Ilango je eden od teh mladih raziskovalcev – v svojih prvih treh letih podiplomskega študija je napadel zastrašujoč odprt problem dokazovanja NP-popolnosti MCSP z dvostransko strategijo: dokazovanje NP-popolnosti za enostavnejši različice MCSP, kot so to storili raziskovalci kompleksnosti vezij, ko so v osemdesetih napadli P proti NP, hkrati pa so dokazali popolnost NP za bolj zapletene različice, ki se intuitivno zdijo težje in jih je zato morda lažje dokazati trde.

Ilango svoje zanimanje za metakompleksnost pripisuje temu Eric Allender, teoretik kompleksnosti na Univerzi Rutgers in eden redkih raziskovalcev, ki so nadaljevali z delom na metakompleksnosti v 2000-ih in zgodnjih 2010-ih. "Njegovo navdušenje je bilo nalezljivo," je dejal Ilango.

Še en mladi raziskovalec, ki ga je navdihnil Allender, je Shuichi Hirahara, zdaj profesor na Nacionalnem inštitutu za informatiko v Tokiu. Medtem ko je leta 2018 še bil podiplomski študent, je Hirahara razkril pravi obseg razmerja med metakompleksnostjo in kompleksnostjo povprečnega primera, ki so ga odkrili Carmosino in njegovi soavtorji. Ti štirje raziskovalci so našli povezavo med povprečno zapletenostjo enega problema – MCSP – in najslabšim primerom zapletenosti drugega – Boolovo učenje. Hirahara je svoje tehnike razvil naprej drift zmanjšanje v najslabšem do povprečnega primera za MCSP. Njegov rezultat nakazuje, da bi bil hipotetični algoritem MCSP v povprečnem primeru, kot je tisti, o katerem so razmišljali Carmosino in njegovi kolegi, dejansko dovolj močan, da bi rešil nekoliko drugačno različico MCSP, ne da bi naredil napake.

Hiraharin rezultat je vznemirljiv, ker mnogi raziskovalci sumijo, da je MCSP NP-popoln, za razliko od vseh drugih problemov, za katere so znana zmanjšanja najslabšega do povprečnega primera. Če lahko Hiraharine rezultate razširijo na vse algoritme povprečnega primera in nato dokažejo, da je MCSP NP-popoln, bi to dokazalo, da ne živimo v Heuristici.

"To bi bil res osupljiv rezultat," je dejal Santhanam.

Dokazati, da je MCSP NP-popoln, se morda zdi težka naloga - navsezadnje je vprašanje odprto že več kot 50 let. Toda po a preboj lani Hirahara, so raziskovalci zdaj veliko bližje, kot bi kdo pričakoval pred nekaj leti.

Hirahara je dokazal NP-popolnost za različico problema, imenovano delni MCSP, pri kateri prezrete določene vnose v vsaki tabeli resnic. Njegov dokaz je temeljil na metodah, ki jih je razvil Ilango, da bi pokazal, da je delni MCSP enakovreden na videz nepovezanemu problemu, ki vključuje kriptografsko tehniko, imenovano deljenje skrivnosti. To je način za razdelitev šifriranega sporočila med več ljudi, tako da ga je mogoče dekodirati le, če določen del njih sodeluje.

Za vsako resnično aplikacijo v kriptografiji bi želeli ta del vedeti vnaprej, vendar s pomočjo dodatnih kriptografskih trikov lahko ustvarite frustrirajoč scenarij, v katerem je težko samo ugotoviti, koliko ljudi mora sodelovati. Hirahara je našel način, kako dokazati, da je ta izmišljena kriptografska težava NP-popolna, in nato pokazal, da dokaz implicira NP-popolnost tudi delnega MCSP.

Ta rezultat je spodbudil raziskovalce metakompleksnosti še bolj kot prejšnje Hiraharino delo, opazili pa so ga tudi drugi raziskovalci - teoretik kompleksnosti in bloger Lance Fortnow ga je poimenoval rezultat leta. To je zato, ker je bilo reševanje takšnih različic računalniških problemov "delne funkcije" ključni vmesni korak v drugih dokazih o popolnosti NP.

"To je neverjetno delo," je dejal Williams. "Vsi so mislili, da so te delne težave približno enake težave kot celotna težava."

Še vedno obstajajo ovire pri dokazovanju popolnosti NP za polno različico MCSP. Vendar nobena ni takšna ovira, ki bi nakazovala, da je potreben povsem nov nabor orodij - morda je le treba najti pravi način za združevanje znanih tehnik. Dokaz bi končno rešil status enega redkih problemov, ki so se upirali klasifikaciji, dokler obstaja teorija kompleksnosti. Po elektronski pošti je Levin zapisal: "Ponižalo bi me, če bi pokazal, da sem neumen, ker tega nisem mogel videti :-)."

Manjkajoči deli

MCSP niti ni edini problem metakompleksnosti, ki je spodbudil velik preboj. Leta 2020 je kriptograf Cornell Tech Prelaz Rafael in njegov podiplomski študent Yanyi Liu odkril povezavo med drugačnim problemom metakompleksnosti in temeljnim kriptografskim protokolom, ki določa mejo med Heuristica in Pessilandom, najslabšim od Impagliazzovih svetov (kjer so NP-popolni problemi težki v smislu povprečnega primera, vendar je kriptografija še vedno nemogoča). Zaradi tega je problem, ki so ga preučevali, glavni kandidat za napad na Pessiland in njihov novejše delo kaže, da bi lahko deloval tudi proti Heuristiki.

"Manjkajo različni deli sestavljanke," je dejal Pass. "Zame je prav čarobno, da so ta polja tako tesno povezana."

Hirahara opozarja, da izzivi še vedno čakajo raziskovalce, ki nameravajo uničiti svetove, ki jih je Impagliazzo pričaral pred 30 leti. "Rad bi povedal, da bosta na neki točki Heuristica in Pessiland izključena, vendar nisem prepričan, kako blizu smo," je dejal.

Mnogi raziskovalci pričakujejo, da bo največja težava premostitev na videz neškodljive vrzeli med dvema različnima modeloma povprečne zapletenosti primerov. Kriptografi običajno preučujejo algoritme povprečnega primera, ki delajo napake v obe smeri, občasno napačno označujejo naključne nize kot psevdonaključne in obratno. Hiraharino zmanjševanje najslabšega v povprečni primer deluje za algoritme povprečnega primera, ki povzročijo samo prvo vrsto napake. Prefinjene razlike, kot je ta, lahko v teoriji zapletenosti naredijo svet razlike. Toda kljub tej oviri in številnim drugim Allender ne more pomagati, da ne bi zvenel kanček zadržanega optimizma.

"Poskušam si ne dovoliti, da bi bil preveč veren, ker je precej dobro uveljavljena evidenca, da nič ne deluje," je dejal. "Toda opažamo veliko res vznemirljivih dogodkov - načinov za premagovanje stvari, ki so bile videti kot ovire."

Če obstaja ena lekcija, ki so se je raziskovalci naučili iz svojih prizadevanj, da bi odgovorili na vprašanje P proti NP - ali celo samo razumeli - je to, da je teorija kompleksnosti sama po sebi kompleksna. Toda ravno zaradi tega izziva je iskanje tako koristno.

"Pravzaprav je super, da je tako težko," je dejal Carmosino. "Nikoli mi ne bo dolgčas."

Opomba urednika: Scott Aaronson je član Revija QuantaJe Svetovalni odbor.