Helpolta kuulostava ongelma tuottaa liian suuria numeroita universumillemme | Quanta-lehti

5-vuotiaat eivät usein ymmärrä kysymyksiä tietojenkäsittelytieteen rajoilla, mutta niin voi tapahtua. Oletetaan esimerkiksi, että Alice-nimisellä päiväkodilla on kaksi omenaa, mutta hän pitää appelsiineista. Onneksi hänen luokkatoverinsa ovat kehittäneet terveellisen hedelmäkauppajärjestelmän tiukasti pakotetuilla valuuttakursseilla: Luovu vaikka omenasta, niin saat banaanin. Pystyykö Alice tekemään joukon kauppoja poimimalla ja purkamalla banaaneja tai cantaloupeja, jotka saavat hänet nauttimaan suosikkihedelmästään?

Se kuulostaa riittävän yksinkertaiselta. "Voit mennä alakouluun ja kertoa [sen] lapsille", sanoi Christoph Haase, tietojenkäsittelytieteilijä Oxfordin yliopistosta. "Ihmiset ajattelevat, että sen täytyy olla helppoa."

Mutta Alicen dilemman taustalla oleva matemaattinen ongelma - jota kutsutaan vektorin lisäysjärjestelmien saavutettavuusongelmaksi - on yllättävän hienovarainen. Vaikka jotkin tapaukset voidaan ratkaista helposti, tietotekniikan tutkijat kamppailivat lähes puoli vuosisataa saadakseen kokonaisvaltaisen käsityksen ongelmasta. Nyt viime vuosien läpimurtojen sarjassa he ovat vakiintuneet tarkasti, kuinka monimutkainen ongelma voi olla.

Osoittautuu, että tämä lapsellinen ongelma on järjettömän, melkein sarjakuvamaisen monimutkainen - niin monimutkainen kuin käytännössä kaikki muut tunnetusti vaikeita laskentaongelmia näyttää lastenleiltä. Yritä mitata tämän ongelman ratkaisemiseen tarvittavat ponnistelut, ja pian kohtaat niin suuria lukuja, että jopa niiden numeroiden laskeminen saa sinut tavoittamaan numeroita, joista et ole koskaan kuullut. Tällaiset luvut kutsuvat usein vertailemaan maailmankaikkeuden mittakaavaa, mutta jopa nuo analogiat jäävät vajaaksi. "Se ei tekisi sille oikeutta", sanoi Georg Zetzsche, tietojenkäsittelytieteilijä Max Planck Institute for Software Systemsissä Kaiserslauternissa, Saksassa. "Universumi on niin pieni."

Ulottuvilla?

Pohjimmiltaan riisuttu saavutettavuusongelma koskee matemaattisia objekteja, joita kutsutaan vektoreiksi, jotka ovat järjestettyjä numerolistoja. Näiden luetteloiden merkintöjä kutsutaan komponenteiksi, ja vektorin komponenttien lukumäärää kutsutaan sen dimensioiksi. Esimerkiksi Alicen hedelmävarasto voidaan kuvata neliulotteisella vektorilla (a, b, c, d), jonka komponentit kertovat kuinka monta omenaa, banaania, cantaloupeja ja appelsiineja hänellä on kulloinkin.

Vektorilisäysjärjestelmä tai VAS on kokoelma vektoreita, jotka edustavat mahdollisia siirtymiä järjestelmän tilojen välillä. Alicelle siirtymävektori (−1, −1, 1, 0) edustaisi omenan ja banaanin vaihtoa melonkiin. VAS:n saavutettavuusongelma kysyy, onko olemassa jokin sallittujen siirtymien yhdistelmä, joka voi viedä sinut tietystä aloitustilasta tiettyyn kohdetilaan – tai matemaattisesti sanottuna, onko olemassa jokin siirtymävektorien summa, joka muuntaa aloitusvektorin kohdevektoriksi. On vain yksi saalis: mikään järjestelmän tilaa kuvaavan vektorin komponentti ei voi koskaan pudota alle nollan.

"Se on hyvin luonnollinen rajoitus todellisuusmallille", sanoi Wojciech Czerwiński, tietojenkäsittelytieteilijä Varsovan yliopistosta. "Sinulla ei voi olla negatiivista määrää omenoita."

Joissakin järjestelmissä on helppo määrittää, onko kohdevektori tavoitettavissa. Mutta näin ei aina ole. Tietojenkäsittelytieteilijöitä kiinnostavat eniten yksinkertaisen näköiset vektorien yhteenlaskujärjestelmät, joissa ei ole selvää, kuinka vaikeaa on määrittää saavutettavuus. Näiden tapausten tutkimiseksi tutkijat aloittavat määrittämällä numeron, joka ilmaisee tietyn järjestelmän koon. Tämä numero, jota edustaa n, sisältää ulottuvuuksien määrän, siirtymien määrän ja muita tekijöitä. Sitten he kysyvät, kuinka nopeasti saavutettavuusongelman vaikeus voi kasvaa n kasvaa suuremmaksi.

Vastatakseen tähän kysymykseen tutkijat käyttävät kahta toisiaan täydentävää lähestymistapaa. Ensin he etsivät esimerkkejä erityisen hankalia vektorien summausjärjestelmistä, joissa saavutettavuuden määrittäminen vaatii jonkin verran vaivaa. Näitä vähimmäistasoja kutsutaan ongelman monimutkaisuuden "alarajoiksi" - he sanovat tutkijoille: "Tietylle hankalimmat järjestelmät n ovat ainakin näin vaikeita."

Toiseksi tutkijat yrittävät asettaa "ylärajoja" - rajoja sille, kuinka vaikeasti saavutettavuus voi olla, jopa kaikkein pirullisimmissa järjestelmissä. Nämä sanovat: "Tietenkin vaikeimmat tapaukset n ovat korkeintaan näin vaikeita." Määrittääkseen tarkasti, kuinka vaikea tavoitettavuus on vaikeimmissa järjestelmissä, tutkijat yrittävät työntää alarajoja ylös ja ylärajoja alaspäin, kunnes he kohtaavat.

Painajaisten juttuja

Vektorilisäysjärjestelmillä on pitkä historia. Tietojenkäsittelytieteilijät ovat käyttäneet niitä 1960-luvulta lähtien mallintaessaan ohjelmia, jotka hajottavat laskennan useisiin pieniin osiin ja työskentelevät näiden osien parissa samanaikaisesti. Tällainen "samanaikainen laskenta" on nyt kaikkialla, mutta tutkijat eivät vieläkään täysin ymmärrä sen matemaattista perustaa.

Vuonna 1976 tietojenkäsittelytieteilijä Richard Lipton otti ensimmäisen askeleen kohti VAS:n saavutettavuusongelman monimutkaisuuden ymmärtämistä. Hän kehitti menetelmän järjestelmien rakentamiseksi, jossa nopein tapa määrittää, onko jokin tila saavutettavissa toisesta, on kartoittaa niiden välinen siirtymäsarja. Tämä antoi hänelle mahdollisuuden käyttää kahden huolellisesti valitun tilan välisen lyhimmän polun pituutta saavutettavuusongelman vaikeuden mittana.

Lipton sitten osoittautui hän pystyi rakentamaan kokojärjestelmän n jossa lyhin polku kahden tilan välillä sisälsi enemmän kuin $lateksi 2^{2^n}$ siirtymää. Tämä merkitsi vastaavaa kaksinkertaista eksponentiaalista alarajaa ponnisteluille, joita vaadittiin saavutettavuuden määrittämiseksi hänen järjestelmissään. Se oli hätkähdyttävä löytö – kaksinkertainen eksponentiaalinen kasvu on tietotekniikan tutkijoiden painajaisia. Todellakin, tutkijat usein hylkäävät jopa tavallisen eksponentiaalisen kasvun, joka haalistuu vertailussa: $lateksi {2^5}= 32 $, mutta $lateksi 2^{2^5} $ on yli 4 miljardia.

Useimmat tutkijat ajattelivat, että Lipton oli keksinyt monimutkaisimmat mahdolliset vektorien summausjärjestelmät, mikä tarkoittaa, että hän oli nostanut alarajaa niin korkealle kuin mahdollista. Ainoa asia, joka siinä tapauksessa puuttuisi, olisi siihen sopiva yläraja – toisin sanoen todiste siitä, ettei voi olla järjestelmää, jossa saavutettavuuden määrittäminen olisi vieläkin vaikeampaa. Mutta kukaan ei osannut todistaa sitä. Tietojenkäsittelytieteilijä Ernst Mayr oli lähimpänä, kun hän osoittautui vuonna 1981, että saavutettavuus on periaatteessa aina mahdollista määrittää missä tahansa vektorinlisäysjärjestelmässä. Mutta hänen todisteensa ei asettanut kvantitatiivista ylärajaa sille, kuinka vaikea ongelma voisi olla. Siellä oli lattia, mutta kattoa ei näkynyt.

"Olin varmasti ajatellut sitä päälle ja pois", Lipton sanoi. "Mutta jonkin ajan kuluttua luovutin, ja sikäli kuin pystyin kertomaan, kukaan ei edistynyt noin 40 vuoteen."

Vuonna 2015 tietojenkäsittelytieteilijät Jérôme Leroux ja Sylvain Schmitz vihdoin perustettu määrällinen yläraja - niin korkea, että tutkijat olettivat sen olevan vain ensimmäinen askel, joka voidaan työntää alas Liptonin alarajan saavuttamiseksi.

Mutta niin ei käynyt. Vuonna 2019 tutkijat löysivät alarajan, joka on paljon korkeampi kuin Liptonin, mikä nosti vuosikymmenten tavanomaisen viisauden. VAS:n saavutettavuusongelma oli paljon monimutkaisempi kuin kukaan oli odottanut.

Voimien torni

Vuoden 2019 järkyttävä tulos kasvoi epäonnistumisesta. Vuonna 2018 Czerwiński kumosi Leroux'n ja arvelun Filip Mazowiecki, tietojenkäsittelytieteilijä Varsovan yliopistossa, mikä olisi auttanut edistymään liittyvän ongelman ratkaisemisessa. Myöhemmissä keskusteluissa tutkijat osuivat lupaavaan uuteen tapaan rakentaa monimutkaisia ​​vektorinlisäysjärjestelmiä, mikä voisi merkitä uutta alarajaa VAS:n saavutettavuusongelmalle, jossa edistyminen oli pysähtynyt niin kauan.

"Kaikki liittyi mielessäni VAS:n saavutettavuuteen", Czerwiński muisteli. Kevyen opetuskuorman lukukauden aikana hän päätti keskittyä yksinomaan tähän ongelmaan yhdessä Leroux'n, Mazowieckin ja kahden muun tutkijan kanssa. Sławomir Lasota Varsovan yliopistosta ja Ranko Lazić Warwickin yliopistosta.

Muutaman kuukauden kuluttua heidän ponnistelunsa tuottivat tulosta. Czerwiński ja hänen kollegansa osoittivat että he pystyivät rakentamaan vektoreiden summausjärjestelmiä, joissa lyhin polku kahden tilan välillä oli yhteydessä järjestelmän kokoon matemaattisella operaatiolla nimeltä tetratio, joka saa painajaismaisenkin kaksinkertaisen eksponentiaalisen kasvun näyttämään kesyltä.

Tetraatio on suora jatke kuviolle, joka yhdistää matematiikan tutuimmat operaatiot, alkaen yhteenlaskemisesta. Lisää yhteen n kopioita luvusta, ja tulos vastaa tämän luvun kertomista n. Jos kerrotaan yhdessä n kopioita numerosta, joka vastaa eksponentiota tai luvun nostamista numeroon nth teho. Tetrointi, jota usein edustaa ylöspäin osoittava nuolipari, on seuraava vaihe tässä sarjassa: Numeron tetratroiminen n tarkoittaa sen eksponentioimista n kertaa tuottaa voimatorni n tarinoita korkealla.

On vaikea ymmärtää, kuinka nopeasti tetratio karkaa käsistä: $lateksi 2 uparrowuparrow 3$ tai $lateksi 2^{2^2}$ on 16, $lateksi 2 uparrowuparrow 4$ on hieman yli 65,000 2 ja $latex 5 uparrowuparrow 20,000$ on luku, jossa on lähes 2 6 numeroa. On fyysisesti mahdotonta kirjoittaa muistiin kaikkia $lateksi XNUMX uparrowuparrow XNUMX $ numeroita – näin pienessä universumissa elämisen velvollisuus.

Merkittävässä tuloksessaan Czerwiński ja hänen kollegansa osoittivat, että on olemassa kokoisia vektoreiden yhteenlaskujärjestelmiä n missä paras tapa määrittää saavutettavuus on kartoittaa polku, joka sisältää enemmän kuin $lateksia 2 uparrowuparrow n$ siirtymiä, mikä tarkoittaa uutta alarajaa, joka kääpiö Liptonin. Mutta niin päätä pyörittävää kuin tetration onkin, se ei silti ollut viimeinen sana ongelman monimutkaisuudesta.

Quinquagintiljonille ja sen ulkopuolelle 

Vain muutama kuukausi VAS:n saavutettavuuden monimutkaisuuden uudesta alarajasta, Leroux ja Schmitz painettu alas yläraja, jonka he olivat asettaneet kolme vuotta aiemmin, mutta he eivät päässeet tetratioon asti. Sen sijaan he osoittivat, että saavutettavuusongelman monimutkaisuus ei voi kasvaa nopeammin kuin matemaattinen hirviö, jota kutsutaan Ackermann-funktioksi.

Ymmärtääksesi tämän funktion, vie tetration määrittämiseen käytetty kuvio sen synkän johtopäätöksen mukaan. Jakson seuraava operaatio, jota kutsutaan pentaatioksi, edustaa toistuvaa tetratiota; sitä seuraa vielä toinen operaatio (heksaani) toistuvalle viittaukselle ja niin edelleen.

Ackermann-funktio, jota merkitään $lateksi A(n)$, on se, mitä saat, kun siirryt askeleen ylöspäin operaatioiden portaissa jokaisella numerorivin pysähdyksellä: $lateksi A(1) = 1 + 1$, $lateksi A (2) = 2 × 2$, $lateksi A(3) = 3^3$, $lateksi A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ ja niin edelleen. $latex A(4)$:n numeroiden määrä on itsessään valtava luku, joka on suunnilleen yhtä kuin 1 kvvinkvagintiljoona – se on hassu ja harvoin tarvittava nimi ykköselle, jota seuraa 1 nollaa. "Älä ole huolissasi viiden vuoden Ackermannista", neuvoi Javier Esparza, tietojenkäsittelytieteilijä Münchenin teknisestä yliopistosta.

Leroux'n ja Schmitzin tulos jätti suuren eron ala- ja ylärajojen välille – VAS:n saavutettavuusongelman tarkka monimutkaisuus voi olla alueen kummassakin päässä tai missä tahansa siltä väliltä. Czerwiński ei aikonut päästää eroa seisomaan. "Jatkoimme työtä tämän parissa, koska oli selvää, että se on suurin asia, jonka olemme koskaan tehneet elämässämme", hän sanoi.

Lopullinen läpimurto tapahtui vuonna 2021, kun Czerwiński neuvoi toisen vuoden perustutkinto-opiskelijaa nimeltä Łukasz Orlikowski. Hän antoi Orlikowskille yksinkertaisen muunnelman ongelmasta saadakseen hänet vauhtiin, ja Orlikowskin työ auttoi heitä kehittämään uuden tekniikan, joka soveltui myös yleiseen saavutettavuusongelmaan. Se antoi heille mahdollisuuden nosta alarajaa olennaisesti - aina Leroux'n ja Schmitzin Ackermannin ylärajaan saakka. Työskentely itsenäisesti, Leroux sai vastaava tulos suunnilleen samaan aikaan.

Lopuksi tutkijat olivat selvittäneet saavutettavuusongelman todellisen monimutkaisuuden. Czerwińskin, Orlikowskin ja Leroux'n alaraja osoitti, että on olemassa sarja asteittain suurempia vektorien summausjärjestelmiä, joissa lyhin polku kahden tilan välillä kasvaa suhteessa Ackermannin funktioon. Leroux'n ja Schmitzin yläraja osoitti, että saavutettavuusongelma ei voi olla sen monimutkaisempi – ei juurikaan lohdutusta kenellekään, joka toivoo erehtymätöntä käytännön menettelyä sen ratkaisemiseksi. Se on silmiinpistävä esimerkki siitä, kuinka hienovaraisia ​​näennäisesti yksinkertaiset laskennalliset ongelmat voivat olla.

Ei koskaan valmis

Tutkijat ovat jatkaneet VAS:n saavutettavuusongelman tutkimista sen tarkan monimutkaisuuden määrittämisen jälkeen, koska monet kysymyksen variantit jäävät vastaamatta. Esimerkiksi Ackermannin ylä- ja alarajat eivät tee eroa erilaisten lisääntymistapojen välillä n, kuten vektorien dimensioiden lisääminen tai sallittujen siirtymien määrän lisääminen.

Viime aikoina Czerwiński ja hänen kollegansa ovat edistynyt kiusoittelemalla näitä erillisiä vaikutuksia tutkimalla, kuinka nopeasti monimutkaisuus voi kasvaa vektorin lisäysjärjestelmien muunnelmissa, joissa on kiinteä ulottuvuus. Mutta vielä on tehtävää – jopa kolmessa ulottuvuudessa, joissa vektorien yhteenlaskujärjestelmät on helppo visualisoida, saavutettavuusongelman tarkka monimutkaisuus on edelleen tuntematon.

"Tietällä tavalla se on vain noloa meille", Mazowiecki sanoi.

Tutkijat toivovat, että suhteellisen yksinkertaisten tapausten parempi ymmärtäminen auttaa heitä kehittämään uusia työkaluja muiden laskentamallien tutkimiseen, jotka ovat monimutkaisempia kuin vektorien yhteenlaskujärjestelmät. Tällä hetkellä emme tiedä juuri mitään näistä monimutkaisemmista malleista.

"Näen tämän osana erittäin perustavaa laatua olevaa pyrkimystä ymmärtää laskettavuutta", Zetzsche sanoi.

Quanta tekee sarjan kyselyjä palvellakseen paremmin yleisöämme. Ota meidän tietojenkäsittelytieteen lukijakysely ja pääset mukaan voittamaan ilmaiseksi Quanta kauppatavaraa.