Enostavno zveneč problem prinaša številke, prevelike za naše vesolje | Revija Quanta

Ni pogosto, da lahko 5-letniki razumejo vprašanja na mejah računalništva, vendar se lahko zgodi. Recimo, da ima vrtec z imenom Alice dve jabolki, vendar ima raje pomaranče. Na srečo so njeni sošolci razvili zdrav sistem trgovanja s sadjem s strogo uveljavljenimi menjalnimi tečaji: odpovejte se jabolku, recimo, in lahko dobite banano. Ali lahko Alice izvede vrsto poslov, tako da pobere in raztovori banane ali melone, kar jo pripelje do njenega najljubšega sadja?

Sliši se dovolj preprosto. "Lahko greš v osnovno šolo in [to] poveš otrokom," je rekel Christoph Haase, računalničar na Univerzi v Oxfordu. "Ljudje si bodo mislili, 'To mora biti enostavno.'"

Toda matematični problem, na katerem temelji Alicina dilema – imenovan problem dosegljivosti za vektorske sisteme dodajanja – je presenetljivo subtilen. Medtem ko je nekatere primere mogoče zlahka rešiti, so se računalniški znanstveniki skoraj pol stoletja borili, da bi razvili celovito razumevanje problema. Zdaj, v seriji prebojev v zadnjih nekaj letih, so trdno ugotovili, kako zapleten lahko ta problem postane.

Izkazalo se je, da je ta otroški problem absurdno, skoraj karikaturno zapleten – tako zapleten, da praktično vsi drugi slavni težki računski problemi izgleda kot otročja igra. Poskusite količinsko opredeliti trud, ki je potreben za rešitev te težave, in kmalu se boste soočili s tako velikimi številkami, da boste že ob preštevanju njihovih števk posegli po številkah, za katere še niste slišali. Takšne številke pogosto vabijo k primerjavam z obsegom vesolja, vendar tudi te analogije ne uspejo. "To ne bi bilo pravično," je rekel Georg Zetzsche, računalničar na Inštitutu Max Planck za programske sisteme v Kaiserslauternu v Nemčiji. "Vesolje je tako majhno."

V dosegu?

Gledano v bistvo, se problem dosegljivosti nanaša na matematične objekte, imenovane vektorji, ki so urejeni seznami števil. Vnosi na teh seznamih se imenujejo komponente, število komponent v vektorju pa se imenuje njegova dimenzionalnost. Alicin inventar sadja je na primer mogoče opisati s štiridimenzionalnim vektorjem (a, b, c, d), katere komponente predstavljajo, koliko jabolk, banan, melon in pomaranč ima v danem trenutku.

Sistem dodajanja vektorjev ali VAS je zbirka vektorjev, ki predstavljajo možne prehode med stanji v sistemu. Za Alice bi prehodni vektor (−1, −1, 1, 0) predstavljal zamenjavo jabolka in banane za melono. Problem dosegljivosti VAS sprašuje, ali obstaja kakršna koli kombinacija dovoljenih prehodov, ki vas lahko popeljejo iz določenega začetnega stanja v določeno ciljno stanje – ali, v matematičnem smislu, ali obstaja kakšna vsota prehodnih vektorjev, ki pretvori začetni vektor v ciljni vektor. Obstaja samo en ulov: nobena komponenta vektorja, ki opisuje stanje sistema, ne more nikoli pasti pod ničlo.

"To je zelo naravna omejitev za model realnosti," je dejal Wojciech Czerwiński, računalničar na Univerzi v Varšavi. "Ne morete imeti negativnega števila jabolk."

V nekaterih sistemih je enostavno ugotoviti, ali je ciljni vektor dosegljiv. Vendar ni vedno tako. Računalničarje najbolj zanimajo preprosti sistemi vektorskega dodajanja, pri katerih ni očitno, kako težko je določiti dosegljivost. Za preučevanje teh primerov raziskovalci začnejo z opredelitvijo števila, ki kvantificira velikost danega sistema. To število, ki ga predstavlja n, zajema število dimenzij, število prehodov in druge dejavnike. Nato vprašajo, kako hitro se lahko poveča težavnost problema dosegljivosti n raste večja.

Za odgovor na to vprašanje raziskovalci uporabljajo dva komplementarna pristopa. Najprej iščejo primere posebej zapletenih sistemov dodajanja vektorjev, pri katerih določanje dosegljivosti zahteva nekaj minimalnega truda. Te najnižje ravni se imenujejo "spodnje meje" kompleksnosti problema - raziskovalcem pravijo: "Najtežje sisteme za dano n so vsaj tako težki."

Drugič, raziskovalci poskušajo določiti "zgornje meje" - meje, kako težko dosegljivost je lahko dosegljiva, tudi v najbolj hudičevih sistemih. Te pravijo: »Najtežje primerke za dano n so kvečjemu tako težki." Da bi natančno določili, kako težka je dosegljivost v najzahtevnejših sistemih, poskušajo raziskovalci potisniti spodnje meje navzgor in zgornje navzdol, dokler se ne srečajo.

The Stuff of Nightmares

Sistemi dodajanja vektorjev imajo dolgo zgodovino. Od šestdesetih let prejšnjega stoletja jih računalniški znanstveniki uporabljajo za modeliranje programov, ki razdelijo izračun na veliko majhnih kosov in delajo na teh delih hkrati. Tovrstno "hkratno računalništvo" je zdaj vseprisotno, vendar raziskovalci še vedno ne razumejo popolnoma njegovih matematičnih temeljev.

Leta 1976 informatik Richard Lipton naredil prvi korak k razumevanju zapletenosti problema dosegljivosti VAS. Razvil je postopek za konstruiranje sistemov, pri katerem je najhitrejši način za ugotavljanje, ali je eno stanje dosegljivo iz drugega, ta, da narišemo zaporedje prehodov med njima. To mu je omogočilo, da je kot merilo težavnosti problema dosegljivosti uporabil dolžino najkrajše poti med dvema skrbno izbranima stanjema.

Lipton torej dokazano lahko je zgradil sistem velikosti n pri kateri je najkrajša pot med dvema stanjema vključevala več kot prehode $latex 2^{2^n}$. To je impliciralo ustrezno dvojno eksponentno spodnjo mejo napora, potrebnega za določitev dosegljivosti v njegovih sistemih. To je bilo presenetljivo odkritje - dvojna eksponentna rast je nočna mora računalničarjev. Dejansko se raziskovalci pogosto zadržujejo celo pri običajni eksponentni rasti, ki je v primerjavi z njo bleda: $latex {2^5}= 32$, $latex 2^{2^5}$ pa je več kot 4 milijarde.

Večina raziskovalcev je menila, da je Lipton zakuhal najbolj zapletene možne vektorske sisteme dodajanja, kar pomeni, da je dvignil spodnjo mejo tako visoko, kot je lahko. Edina stvar, ki bi v tem primeru manjkala, bi bila zraven zgornja meja - to je dokaz, da ne more obstajati sistem, v katerem bi bilo določanje dosegljivosti še težje. A tega nihče ni znal dokazati. Še najbolj približal računalničar Ernst Mayr, ko je dokazano leta 1981, da je načeloma vedno mogoče določiti dosegljivost v katerem koli vektorskem sistemu dodajanja. Toda njegov dokaz ni postavil nobene kvantitativne zgornje meje glede tega, kako močan bi lahko bil problem. Bila so tla, stropa pa ni bilo videti.

"Vsekakor sem razmišljal o tem," je dejal Lipton. "Toda čez nekaj časa sem obupal in kolikor sem lahko ugotovil, nihče ni napredoval v približno 40 letih."

Leta 2015 so računalničarji Jérôme Leroux in Sylvain Schmitz dokončno ustanovljena kvantitativno zgornjo mejo — ena tako visoka, da so raziskovalci domnevali, da je le prva stopnica, ki bi jo lahko potisnili navzdol, da bi dosegli Liptonovo spodnjo mejo.

Ampak to se ni zgodilo. Leta 2019 so raziskovalci odkrili spodnjo mejo, veliko višjo od Liptonove, s čimer so ovrgli desetletja konvencionalne modrosti. Problem dosegljivosti VAS je bil veliko bolj zapleten, kot je kdo pričakoval.

Stolp moči

Šokanten rezultat leta 2019 je zrasel iz neuspeha. Leta 2018 je Czerwiński ovrgel domnevo Lerouxa in Filip Mazowiecki, računalniški znanstvenik, ki je zdaj na Univerzi v Varšavi, bi to pomagalo doseči napredek pri sorodnem problemu. V poznejših razpravah so raziskovalci naleteli na obetaven nov način za konstruiranje izjemno kompleksnih vektorskih sistemov dodajanja, kar bi lahko pomenilo novo spodnjo mejo problema dosegljivosti VAS, kjer je napredek tako dolgo zastal.

»Vse, kar je bilo v mojih mislih povezano z dosegljivostjo VAS,« se je spominjal Czerwiński. Med semestrom z majhno obremenitvijo poučevanja se je odločil, da se osredotoči izključno na ta problem, skupaj z Lerouxom, Mazowieckim in dvema drugima raziskovalcema - Sławomir Lasota Univerze v Varšavi in Ranko Lazić Univerze v Warwicku.

Po nekaj mesecih je bil njihov trud poplačan. Czerwiński in njegovi sodelavci Dokazano da bi lahko zgradili sisteme vektorskega dodajanja, v katerih je bila najkrajša pot med dvema stanjema povezana z velikostjo sistema z matematično operacijo, imenovano tetracija, zaradi katere se celo nočna mora dvojne eksponentne rasti zdi krotka.

Tetracija je preprosta razširitev vzorca, ki povezuje najbolj poznane operacije v matematiki, začenši s seštevanjem. Dodajte skupaj n kopije števila, rezultat pa je enakovreden množenju tega števila s n. Če pomnožite skupaj n kopije števila, kar je enakovredno potenciranju ali dvigu števila na nmoč. Tetracija, pogosto predstavljena s parom puščic, usmerjenih navzgor, je naslednji korak v tem zaporedju: tetracija števila z n pomeni potenciranje n krat ustvariti stolp moči n zgodbe visoke.

Težko si je zamisliti, kako hitro tetracija uide izpod nadzora: $latex 2 uparrowuparrow 3$ ali $latex 2^{2^2}$ je 16, $latex 2 uparrowuparrow 4$ je nekaj več kot 65,000 in $latex 2 uparrowuparrow 5$ je številka s skoraj 20,000 ciframi. Fizično je nemogoče zapisati vse števke $latex 2 uparrowuparrow 6$ – to je težava življenja v tako majhnem vesolju.

V svojem pomembnem rezultatu so Czerwiński in njegovi kolegi dokazali, da obstajajo vektorski sistemi dodajanja velikosti n kjer je najboljši način za določitev dosegljivosti načrtovanje poti, ki vključuje več kot $latex 2 uparrowuparrow n$ prehodov, kar implicira novo spodnjo mejo, ki je zasenčila Liptonovo. Toda ne glede na to, kako tetracija se vrti v glavi, še vedno ni bila zadnja beseda o kompleksnosti problema.

Do Quinquagintillion in naprej 

Le nekaj mesecev po šokantni novi spodnji meji zapletenosti dosegljivosti VAS sta Leroux in Schmitz potisnjen navzdol zgornjo mejo, ki so jo določili tri leta prej, vendar niso prišli vse do tetracije. Namesto tega so dokazali, da kompleksnost problema dosegljivosti ne more rasti hitreje kot matematična pošast, imenovana Ackermannova funkcija.

Da bi razumeli to funkcijo, pripeljite vzorec, uporabljen za definiranje tetracije, do mračnega zaključka. Naslednja operacija v zaporedju, imenovana pentacija, predstavlja ponavljajočo se tetracijo; sledi še ena operacija (heksacija) za ponavljajočo se pentacijo itd.

Ackermannova funkcija, označena z $latex A(n)$, je tisto, kar dobite, ko se premaknete za eno stopnjo navzgor po tej lestvici operacij z vsakim postankom na številski premici: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ in tako naprej. Število števk v $latex A(4)$ je samo po sebi kolosalno število, približno enako 1 kvinkvagintilijonu — to je muhasto in redko potrebno ime za 1, ki mu sledi 153 ničel. »Ne skrbite za Ackermanna od 5,« svetuje Javier Esparza, računalničar na Tehnični univerzi v Münchnu.

Rezultat Lerouxa in Schmitza je pustil veliko vrzel med spodnjo in zgornjo mejo - natančna kompleksnost problema dosegljivosti VAS bi lahko ležala na obeh koncih razpona ali kjer koli vmes. Czerwiński ni nameraval pustiti te vrzeli. »Še naprej smo delali na tem, ker je bilo jasno, da je to največja stvar, ki smo jo naredili v življenju,« je dejal.

Končni preboj se je zgodil leta 2021, ko je Czerwiński svetoval študentu drugega letnika dodiplomskega študija po imenu Łukasz Orlikowski. Orlikowskemu je dodelil preprosto različico problema, da bi ga pospešil, delo Orlikowskega pa je pomagalo razviti novo tehniko, ki je veljala tudi za splošni problem dosegljivosti. To jim je omogočilo dvigniti spodnjo mejo bistveno — vse do Lerouxove in Schmitzove Ackermannove zgornje meje. Leroux je delal neodvisno enakovreden rezultat približno v istem času.

Končno so raziskovalci ugotovili resnično kompleksnost problema dosegljivosti. Spodnja meja Czerwińskega, Orlikowskega in Lerouxa je pokazala, da obstaja zaporedje progresivno večjih sistemov dodajanja vektorjev, v katerih najkrajša pot med dvema stanjema raste sorazmerno z Ackermannovo funkcijo. Zgornja meja Lerouxa in Schmitza je pokazala, da težava dosegljivosti ne more biti bolj zapletena od tega – malo tolažbe za vsakogar, ki upa na nezmotljiv praktični postopek za njeno rešitev. To je osupljiva ilustracija, kako subtilni so lahko na videz preprosti računski problemi.

Nikoli dokončano

Raziskovalci so nadaljevali s preučevanjem problema dosegljivosti VAS, potem ko so ugotovili njegovo natančno zapletenost, saj številne različice vprašanja ostajajo neodgovorjene. Ackermannova zgornja in spodnja meja na primer ne razlikujeta med različnimi načini povečanja n, kot je povečanje dimenzionalnosti vektorjev ali povečanje števila dovoljenih prehodov.

Pred kratkim so Czerwiński in njegovi kolegi napredoval ločevanje teh različnih učinkov s preučevanjem, kako hitro se lahko kompleksnost poveča v različicah sistemov dodajanja vektorjev s fiksno dimenzijo. Vendar je treba storiti še več - tudi v treh dimenzijah, kjer je vektorske sisteme dodajanja enostavno vizualizirati, natančna kompleksnost problema dosegljivosti ostaja neznana.

"Na nek način nam je to samo neprijetno," je dejal Mazowiecki.

Raziskovalci upajo, da jim bo boljše razumevanje sorazmerno preprostih primerov pomagalo razviti nova orodja za preučevanje drugih modelov računanja, ki so bolj izpopolnjeni kot sistemi dodajanja vektorjev. Trenutno o teh bolj izpopolnjenih modelih ne vemo skoraj nič.

"Na to gledam kot na del zelo temeljnega prizadevanja za razumevanje izračunljivosti," je dejal Zetzsche.

Quanta izvaja vrsto anket, da bi bolje služil svojemu občinstvu. Vzemite našo anketa bralcev računalništva in vključeni boste v brezplačno zmago Quanta trgovsko blago.