Lihtsalt kõlav probleem annab meie universumi jaoks liiga suured numbrid | Ajakiri Quanta

Ei juhtu sageli, et 5-aastased saavad aru arvutiteaduse piirimail olevatest küsimustest, kuid see võib juhtuda. Oletame näiteks, et lasteaialapsel nimega Alice on kaks õuna, kuid ta eelistab apelsine. Õnneks on tema klassikaaslased välja töötanud tervisliku puuviljakaubanduse süsteemi, mille vahetuskursid on rangelt jõustatud: ütleme, et loobu õunast ja saad banaani. Kas Alice saab sooritada mitmeid tehinguid, korjates ja maha banaane või kantalupe, mis viib ta oma lemmikpuuviljani?

See kõlab piisavalt lihtsalt. "Võite minna algkooli ja rääkida [seda] lastele," ütles Christoph Haase, Oxfordi ülikooli arvutiteadlane. "Inimesed arvavad, et see peab olema lihtne."

Kuid Alice'i dilemma aluseks olev matemaatikaprobleem, mida nimetatakse vektorite liitmise süsteemide ligipääsetavuse probleemiks, on üllatavalt peen. Kuigi mõningaid juhtumeid saab hõlpsasti lahendada, nägid arvutiteadlased peaaegu pool sajandit vaeva, et probleemist kõikehõlmavalt mõista. Nüüd on nad viimaste aastate jooksul läbimurrete käigus kindlalt kindlaks teinud, kui keeruliseks see probleem võib muutuda.

Selgub, et see lapsemeelne probleem on absurdselt, peaaegu karikatuurilikult keeruline — nii keeruline, et praktiliselt kõik muu kuulsalt rasked arvutusprobleemid näeb välja nagu lapsemäng. Proovige mõõta selle probleemi lahendamiseks vajalikku jõupingutust ja peagi seisate silmitsi nii suurte numbritega, et isegi nende numbreid lugedes jõuate numbriteni, millest te pole kunagi kuulnudki. Sellised numbrid kutsuvad sageli esile võrdlust universumi mastaabiga, kuid isegi need analoogiad jäävad alla. "See ei teeks õiglust," ütles Georg Zetzsche, Saksamaal Kaiserslauternis asuva Max Plancki Tarkvarasüsteemide Instituudi arvutiteadlane. "Universum on nii väike."

Käeulatuses?

Sisuliselt eemaldatuna puudutab ligipääsetavusprobleem matemaatilisi objekte, mida nimetatakse vektoriteks ja mis on järjestatud arvude loendid. Nendes loendites olevaid kirjeid nimetatakse komponentideks ja komponentide arvu vektoris nimetatakse selle dimensiooniks. Näiteks Alice'i puuviljavaru saab kirjeldada neljamõõtmelise vektoriga (a, b, c, d), mille komponendid näitavad, kui palju õunu, banaane, kantalupe ja apelsine tal igal ajahetkel on.

Vektorite liitmise süsteem ehk VAS on vektorite kogum, mis esindab võimalikke üleminekuid süsteemi olekute vahel. Alice'i jaoks tähistaks üleminekuvektor (-1, -1, 1, 0) õuna ja banaani vahetust kantaluubi vastu. VAS-i juurdepääsetavuse probleem küsib, kas on olemas mingi lubatud üleminekute kombinatsioon, mis võib viia teid konkreetsest algolekust konkreetsesse sihtolekusse – või matemaatilises mõttes, kas on olemas üleminekuvektorite summa, mis teisendab lähtevektori sihtvektoriks. Siin on vaid üks konks: ükski süsteemi olekut kirjeldava vektori komponent ei saa kunagi langeda alla nulli.

"See on reaalsusmudeli jaoks väga loomulik piirang," ütles Wojciech Czerwiński, Varssavi ülikooli arvutiteadlane. "Teil ei saa olla negatiivset õunte arvu."

Mõnes süsteemis on lihtne kindlaks teha, kas sihtvektor on kättesaadav. Kuid see pole alati nii. Arvutiteadlasi huvitavad enim lihtsa välimusega vektorite liitmise süsteemid, milles pole ilmne, kui raske on ligipääsetavust määrata. Nende juhtumite uurimiseks alustavad teadlased arvu määratlemisega, mis määrab antud süsteemi suuruse. See number, mida esindab n, hõlmab mõõtmete arvu, üleminekute arvu ja muid tegureid. Seejärel küsivad nad, kui kiiresti võib ligipääsetavuse probleemi raskus suureneda n kasvab suuremaks.

Sellele küsimusele vastamiseks kasutavad teadlased kahte üksteist täiendavat lähenemisviisi. Esiteks otsivad nad näiteid eriti keerulistest vektorite liitmissüsteemidest, kus ligipääsetavuse määramine nõuab minimaalset pingutust. Neid miinimumtasemeid nimetatakse probleemi keerukuse "alumisteks piirideks" - nad ütlevad teadlastele: "Kindla kõige keerulisemad süsteemid n on vähemalt nii rasked."

Teiseks püüavad teadlased kehtestada "ülemised piirid" - piirangud sellele, kui raskesti ligipääsetav võib olla isegi kõige kuratlikumates süsteemides. Need ütlevad: "Kõige keerulisemad juhtumid antud jaoks n on kõige rohkem nii rasked." Et täpselt kindlaks teha, kui raske on juurdepääsetavus kõige keerulisemates süsteemides, proovivad teadlased lükata alumisi piire üles ja ülemisi piire alla, kuni nad kohtuvad.

Õudusunenägude värk

Vektorite liitmise süsteemidel on pikk ajalugu. Alates 1960. aastatest on arvutiteadlased neid kasutanud programmide modelleerimiseks, mis jagavad arvutuse paljudeks väikesteks tükkideks ja töötavad nende osadega samaaegselt. Seda tüüpi "samaaegne andmetöötlus" on praegu üldlevinud, kuid teadlased ei mõista endiselt täielikult selle matemaatilisi aluseid.

1976. aastal arvutiteadlane Richard Lipton astus esimese sammu VAS-i juurdepääsetavuse probleemi keerukuse mõistmiseks. Ta töötas välja süsteemide konstrueerimise protseduuri, mille puhul kiireim viis kindlaks teha, kas üks olek on teisest saavutatav, on kaardistada nendevaheline üleminekute jada. See võimaldas tal kasutada kahe hoolikalt valitud oleku vahelise lühima tee pikkust ligipääsetavuse probleemi raskusastme mõõtmiseks.

Lipton siis tõestatud ta oskas konstrueerida suuruse süsteemi n milles lühim tee kahe oleku vahel hõlmas rohkem kui $lateks 2^{2^n}$ üleminekut. See tähendas tema süsteemides ligipääsetavuse määramiseks vajalike jõupingutuste vastavat topelteksponentsiaalset alampiiri. See oli jahmatav avastus – topelteksponentsiaalne kasv on arvutiteadlaste õudusunenägude värk. Tõepoolest, teadlased kalduvad sageli kõrvale isegi tavalisest eksponentsiaalsest kasvust, mis kahvatub võrdluses: $lateks {2^5}= 32 $, kuid $lateks 2^{2^5} $ on üle 4 miljardi.

Enamik teadlasi arvas, et Lipton oli valmistanud kõige keerulisemad võimalikud vektorite liitmise süsteemid, mis tähendab, et ta tõstis alumise piiri nii kõrgele kui võimalik. Ainus, mis sel juhul puudu oleks, oleks sellega kaasas käiv ülempiir – see tähendab, et ei saa olla süsteemi, kus ligipääsetavuse määramine oleks veelgi raskem. Kuid keegi ei teadnud, kuidas seda tõestada. Arvutiteadlane Ernst Mayr jõudis kõige lähemale, kui ta tõestatud aastal 1981, et alati on põhimõtteliselt võimalik määrata ligipääsetavust mis tahes vektorite liitmise süsteemis. Kuid tema tõestus ei seadnud kvantitatiivset ülempiiri sellele, kui raske probleem võib olla. Põrand oli, aga lage ei paistnud.

"Kindlasti mõtlesin selle peale ja välja," ütles Lipton. "Kuid mõne aja pärast andsin alla ja niipalju kui võisin öelda, ei teinud keegi umbes 40 aasta jooksul edusamme."

2015. aastal arvutiteadlased Jérôme Leroux ja Sylvain Schmitz lõpuks kehtestatud kvantitatiivne ülempiir - üks nii kõrge, et teadlased eeldasid, et see on vaid esimene samm, mida saab Liptoni alampiiri saavutamiseks alla lükata.

Aga nii see ei juhtunud. 2019. aastal avastasid teadlased Liptoni omast palju kõrgema alampiiri, mis tõstab aastakümnete pikkuse tavapärase tarkuse. VAS-i juurdepääsetavuse probleem oli palju keerulisem, kui keegi oleks oodanud.

Võimude torn

2019. aasta šokeeriv tulemus kasvas välja ebaõnnestumisest. 2018. aastal lükkas Czerwiński ümber Leroux’ ja Leroux’ oletuse Filip Mazowiecki, praegu Varssavi ülikoolis töötav arvutiteadlane, mis oleks aidanud sellega seotud probleemi lahendamisel edusamme teha. Järgnevates aruteludes leidsid teadlased paljutõotava uue viisi ekstrakomplekssete vektorite liitmise süsteemide ehitamiseks, mis võib viidata VAS-i ligipääsetavuse probleemile uuele alampiirile, kus edusammud olid nii kaua peatunud.

"Kõik seostus minu meelest VAS-i ligipääsetavusega," meenutas Czerwiński. Kerge õppekoormusega semestri jooksul otsustas ta koos Leroux’, Mazowiecki ja veel kahe teadlasega keskenduda ainult sellele probleemile — Sławomir Lasota Varssavi ülikoolist ja Ranko Lazić Warwicki ülikoolist.

Mõne kuu pärast tasusid nende pingutused vilja. Czerwiński ja tema kolleegid Näidatud et nad võiksid konstrueerida vektorite liitmise süsteeme, milles lühim tee kahe oleku vahel oli seotud süsteemi suurusega matemaatilise operatsiooniga, mida nimetatakse tetratsiooniks, mis muudab isegi painajaliku topelteksponentsiaalse kasvu taltsaks.

Tetreerimine on mustri sirgjooneline laiendus, mis ühendab matemaatikas kõige tuttavamaid tehteid, alustades liitmisest. Lisa kokku n arvu koopiad ja tulemus võrdub selle arvu korrutamisega n. Kui korrutada kokku n arvu koopiad, mis on samaväärne astendamisega või arvu tõstmisega nvõimsus. Tetreerimine, mida sageli kujutab ülespoole suunatud noolte paar, on selle järjestuse järgmine samm: arvu tetramine n tähendab selle astendamist n korda, et toota võimude torn n lugusid kõrgel.

Raske on mõistatada, kui kiiresti tetratsioon käest ära läheb: $latex 2 uparrowuparrow 3$ või $latex 2^{2^2}$ on 16, $latex 2 uparrowuparrow 4$ on veidi üle 65,000 2 ja $latex 5 uparrowuparrow 20,000$ on peaaegu 2 6 numbriga arv. Füüsiliselt on võimatu üles kirjutada kõiki numbreid $latex XNUMX uparrowuparrow XNUMX$ — nii väikeses universumis elamise kohustus.

Czerwiński ja tema kolleegid tõestasid oma märgilises tulemuses, et on olemas suurusega vektorite liitmise süsteemid n kus parim viis ligipääsetavuse määramiseks on kaardistada tee, mis hõlmab rohkem kui $latex 2 uparrowuparrow n$ üleminekuid, mis viitab uuele alampiirile, mis jäi Liptoni omast väiksemaks. Kuid nii peadpööritav kui tetratsioon ka pole, ei olnud see siiski lõplik sõna probleemi keerukuse kohta.

Quinquagintiljonile ja kaugemale 

Vaid paar kuud pärast VAS-i ligipääsetavuse keerukuse šokeerivat uut alampiiri, Leroux ja Schmitz alla surutud ülemine piir, mille nad kehtestasid kolm aastat varem, kuid nad ei jõudnud tetratsioonini. Selle asemel tõestasid nad, et ligipääsetavuse probleemi keerukus ei saa kasvada kiiremini kui matemaatiline koletis, mida nimetatakse Ackermanni funktsiooniks.

Selle funktsiooni mõistmiseks viige tetratsiooni määratlemiseks kasutatud muster selle sünge järelduseni. Jada järgmine tehe, mida nimetatakse pentatsiooniks, tähistab korduvat tetratsiooni; sellele järgneb järjekordne tehte (heksatsioon) korduvaks pentatsiooniks jne.

Ackermanni funktsioon, tähisega $latex A(n)$, on see, mille saate, kui liigute sellel tehteredelil sammu võrra ülespoole iga arvurea peatusega: $lateks A(1) = 1 + 1$, $lateks A (2) = 2 × 2$, $lateks A(3) = 3^3$, $lateks A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ jne. Numbrite arv väärtuses $latex A(4)$ on iseenesest kolossaalne arv, mis on ligikaudu võrdne 1 kvinkvagintiljoniga – see on kummaline ja harva vajalik nimi 1-le, millele järgneb 153 nulli. "Ära muretse 5-aastase Ackermanni pärast," soovitas Javier Esparza, Müncheni tehnikaülikooli arvutiteadlane.

Leroux’ ja Schmitzi tulemus jättis alumise ja ülemise piiri vahele suure lõhe – VAS-i ligipääsetavuse probleemi täpne keerukus võib asuda vahemiku kummaski otsas või kusagil vahepeal. Czerwiński ei kavatsenud sellel vahel püsida. "Me jätkasime selle kallal töötamist, sest oli selge, et see on suurim asi, mida me oma elus teinud oleme," ütles ta.

Lõplik läbimurre toimus 2021. aastal, samal ajal kui Czerwiński nõustas bakalaureuseõppe teise kursuse üliõpilast nimega Łukasz Orlikowski. Ta määras Orlikowskile probleemi lihtsa variandi, et teda kiirendada, ja Orlikowski töö aitas neil kahel välja töötada uue tehnika, mis kehtis ka üldise ligipääsetavuse probleemi puhul. See võimaldas neil tõsta alumist piiri sisuliselt – kuni Leroux’ ja Schmitzi Ackermanni ülempiirini. Iseseisvalt töötades sai Leroux samaväärne tulemus umbes samal ajal.

Lõpuks olid teadlased kindlaks teinud ligipääsetavuse probleemi tõelise keerukuse. Czerwiński, Orlikowski ja Leroux' alumine piir näitas, et on olemas järjest suuremate vektorite liitmise süsteemide jada, milles lühim tee kahe oleku vahel kasvab proportsionaalselt Ackermanni funktsiooniga. Leroux’ ja Schmitzi ülempiir näitas, et ligipääsetavuse probleem ei saa sellest keerulisemaks minna – vähe lohutust igaühele, kes loodab selle lahendamiseks eksimatut praktilist protseduuri. See on rabav näide sellest, kui peened näiliselt lihtsad arvutusprobleemid võivad olla.

Pole kunagi lõpetatud

Teadlased on jätkanud VAS-i kättesaadavuse probleemi uurimist pärast selle täpse keerukuse kindlaksmääramist, kuna paljud küsimuse variandid jäävad vastuseta. Näiteks Ackermanni ülemine ja alumine piir ei tee vahet erinevatel suurendamisviisidel n, nagu vektorite mõõtmete suurendamine või lubatud üleminekute arvu suurendamine.

Viimasel ajal on Czerwiński ja tema kolleegid edusamme teinud õrritades neid eristavaid efekte, uurides, kui kiiresti võib keerukus suureneda fikseeritud mõõtmetega vektorite liitmissüsteemide variantides. Kuid teha on veel rohkem – isegi kolmes mõõtmes, kus vektorite liitmise süsteeme on lihtne visualiseerida, jääb ligipääsetavuse probleemi täpne keerukus teadmata.

"Mõnes mõttes on see meie jaoks lihtsalt piinlik," ütles Mazowiecki.

Teadlased loodavad, et suhteliselt lihtsate juhtumite parem mõistmine aitab neil välja töötada uusi tööriistu, et uurida teisi arvutusmudeleid, mis on keerukamad kui vektorite liitmise süsteemid. Praegu ei tea me nendest keerukamatest mudelitest peaaegu midagi.

"Ma näen seda osana väga põhjapanevatest püüdlustest mõista arvutatavust, " ütles Zetzsche.

Quanta viib läbi mitmeid küsitlusi, et meie vaatajaskonda paremini teenindada. Võtke meie informaatika lugejaküsitlus ja teid osaletakse tasuta võitmiseks Quanta kaubad.