Et let lydende problem giver tal for store til vores univers | Quanta Magasinet

Det er ikke ofte, at 5-årige kan forstå spørgsmål ved datalogiens grænser, men det kan ske. Antag for eksempel, at en børnehave ved navn Alice har to æbler, men hun foretrækker appelsiner. Heldigvis har hendes klassekammerater udviklet et sundt frugthandelssystem med strengt håndhævede valutakurser: Giv op et æble, for eksempel, og du kan få en banan. Kan Alice udføre en række handler ved at samle bananer eller cantaloupes op og af, der får hende til hendes yndlingsfrugt?

Det lyder simpelt nok. "Du kan gå i folkeskolen og fortælle [det til] børn," sagde Christoph Haase, en datalog ved University of Oxford. "Folk vil tænke, 'det må være nemt'."

Men det matematiske problem, der ligger til grund for Alices dilemma - kaldet tilgængelighedsproblemet for vektoradditionssystemer - er overraskende subtilt. Mens nogle sager let kan løses, kæmpede computerforskere i næsten et halvt århundrede for at udvikle en omfattende forståelse af problemet. Nu, i en række af gennembrud i løbet af de sidste par år, har de slået fast, præcis hvor komplekst det problem kan blive.

Det viser sig, at dette barnlige problem er absurd, næsten tegneserieagtigt komplekst - så komplekst, at praktisk talt alle andre berømte hårde beregningsproblemer ligne, ja, barneleg. Prøv at kvantificere den indsats, der kræves for at løse dette problem, og snart vil du stå over for tal så store, at selv tælle deres cifre vil få dig til at nå ud til tal, du aldrig har hørt om. Sådanne tal inviterer ofte til sammenligninger med universets skala, men selv disse analogier kommer til kort. "Det ville ikke gøre det retfærdigt," sagde Georg Zetzsche, en datalog ved Max Planck Institute for Software Systems i Kaiserslautern, Tyskland. "Universet er så lille."

Indenfor rækkevidde?

Strippet til dets essens handler tilgængelighedsproblemet om matematiske objekter kaldet vektorer, som er ordnede lister med tal. Indtastningerne i disse lister kaldes komponenter, og antallet af komponenter i en vektor kaldes dens dimensionalitet. Alices frugtbeholdning kan for eksempel beskrives ved en firedimensionel vektor (a, b, c, d), hvis komponenter repræsenterer hvor mange æbler, bananer, cantaloupes og appelsiner hun har på et givet tidspunkt.

Et vektoradditionssystem, eller VAS, er en samling af vektorer, der repræsenterer de mulige overgange mellem tilstande i et system. For Alice ville overgangsvektoren (−1, −1, 1, 0) repræsentere udvekslingen af ​​et æble og en banan med en cantaloupe. VAS-tilgængelighedsproblemet spørger, om der er en kombination af tilladte overgange, der kan tage dig fra en specifik starttilstand til en specifik måltilstand - eller i matematiske termer, om der er nogen sum af overgangsvektorer, der transformerer startvektoren til målvektoren. Der er kun én hak: Ingen komponent af vektoren, der beskriver systemets tilstand, kan nogensinde falde til under nul.

"Det er en meget naturlig begrænsning for en model af virkeligheden," sagde Wojciech Czerwiński, en datalog ved universitetet i Warszawa. "Du kan ikke have et negativt antal æbler."

I nogle systemer er det nemt at afgøre, om målvektoren er tilgængelig. Men det er ikke altid tilfældet. Dataloger er mest interesseret i simple vektoradditionssystemer, hvor det ikke er indlysende, hvor svært det er at bestemme tilgængelighed. For at studere disse tilfælde starter forskere med at definere et tal, der kvantificerer størrelsen af ​​et givet system. Dette tal, repræsenteret ved n, omfatter antallet af dimensioner, antallet af overgange og andre faktorer. De spørger så, hvor hurtigt sværhedsgraden af ​​tilgængelighedsproblemet kan stige som n vokser sig større.

For at besvare det spørgsmål bruger forskere to komplementære tilgange. Først søger de efter eksempler på særligt vanskelige vektoradditionssystemer, hvor bestemmelse af tilgængelighed kræver et vist minimumsniveau af indsats. Disse minimumsniveauer kaldes "nedre grænser" for kompleksiteten af ​​problemet - de siger til forskere, "De vanskeligste systemer for en given given n er i det mindste så svære."

For det andet forsøger forskere at etablere "øvre grænser" - grænser for, hvor svær tilgængelighed overhovedet kan blive, selv i de mest djævelske systemer. Disse siger, "De vanskeligste tilfælde for en given n er højst så hårde." For at bestemme præcist, hvor svært tilgængeligheden er i de vanskeligste systemer, forsøger forskere at skubbe nedre grænser op og øvre grænser ned, indtil de mødes.

The Stuff of Nightmares

Vektoradditionssystemer har en lang historie. Siden 1960'erne har dataloger brugt dem til at modellere programmer, der deler en beregning op i mange små stykker og arbejder på disse stykker samtidigt. Denne form for "concurrent computing" er nu allestedsnærværende, men forskere forstår stadig ikke fuldt ud dets matematiske grundlag.

I 1976, datalogen Richard Lipton tog det første skridt mod at forstå kompleksiteten af ​​VAS-problemet. Han udviklede en procedure til at konstruere systemer, hvor den hurtigste måde at bestemme, om en tilstand er tilgængelig fra en anden, er at kortlægge en sekvens af overgange mellem dem. Det gjorde det muligt for ham at bruge længden af ​​den korteste vej mellem to omhyggeligt udvalgte tilstande som et mål for vanskeligheden ved tilgængelighedsproblemet.

Lipton så bevist han kunne konstruere et system af størrelse n hvor den korteste vej mellem to tilstande involverede mere end $latex 2^{2^n}$ overgange. Det indebar en tilsvarende dobbelt eksponentiel nedre grænse for den indsats, der kræves for at bestemme tilgængelighed i hans systemer. Det var en opsigtsvækkende opdagelse - dobbelt eksponentiel vækst er stoffet i computerforskeres mareridt. Forskere afviser faktisk ofte selv ved almindelig eksponentiel vækst, som blegner i sammenligning: $latex {2^5}= 32$, men $latex 2^{2^5}$ er over 4 milliarder.

De fleste forskere troede, at Lipton havde lavet de mest komplekse mulige vektoradditionssystemer, hvilket betyder, at han havde hævet den nedre grænse så højt, som den kunne gå. Det eneste, der mangler, i så fald ville være en øvre grænse for at gå med det - det vil sige et bevis på, at der ikke kunne være noget system, hvor det var endnu sværere at bestemme tilgængelighed. Men ingen vidste, hvordan man kunne bevise det. Datalogen Ernst Mayr kom tættest på, da han bevist i 1981, at det i princippet altid er muligt at bestemme tilgængelighed i ethvert vektoradditionssystem. Men hans bevis satte ikke nogen kvantitativ øvre grænse for, hvor svært problemet kunne være. Der var et gulv, men intet loft i sigte.

"Jeg tænkte bestemt over det til og fra," sagde Lipton. "Men efter et stykke tid gav jeg op, og så vidt jeg kunne se var der ingen, der gjorde fremskridt i 40 år."

I 2015, datalogerne Jérôme Leroux , Sylvain Schmitz endelig etableret en kvantitativ øvre grænse - en så høj, at forskerne antog, at det kun var et første skridt, der kunne skubbes ned for at møde Liptons nedre grænse.

Men det er ikke det, der skete. I 2019 opdagede forskere en nedre grænse, der var langt højere end Liptons, hvilket øgede årtiers konventionel visdom. VAS-tilgængelighedsproblemet var langt mere komplekst, end nogen havde regnet med.

Et tårn af magter

Det chokerende 2019-resultat voksede ud af fiasko. I 2018 modbeviste Czerwiński en formodning af Leroux og Filip Mazowiecki, en datalog nu ved universitetet i Warszawa, der ville have hjulpet med at gøre fremskridt med et relateret problem. I efterfølgende diskussioner ramte forskerne på en lovende ny måde at konstruere ekstra-komplekse vektoradditionssystemer, hvilket kunne indebære en ny nedre grænse for VAS-nåbarhedsproblemet, hvor fremskridtet var gået i stå så længe.

"Alt i mit sind var forbundet med VAS-tilgængelighed," huskede Czerwiński. I løbet af et semester med en let undervisningsbelastning besluttede han sig for udelukkende at fokusere på det problem sammen med Leroux, Mazowiecki og to andre forskere — Sławomir Lasota fra universitetet i Warszawa og Ranko Lazić fra University of Warwick.

Efter et par måneder gav deres indsats frugt. Czerwiński og hans kolleger demonstreret at de kunne konstruere vektoradditionssystemer, hvor den korteste vej mellem to tilstande var relateret til systemets størrelse ved en matematisk operation kaldet tetration, der får selv mareridtsagtig dobbelt eksponentiel vækst til at virke tam.

Tetration er en ligefrem forlængelse af et mønster, der forbinder de mest velkendte operationer i matematik, begyndende med addition. Tilføj sammen n kopier af et tal, og resultatet svarer til at gange det tal med n. Hvis man formerer sig sammen n kopier af et tal, der svarer til eksponentiering, eller at hæve tallet til nmagt. Tetration, ofte repræsenteret af et par pile, der peger opad, er næste trin i denne sekvens: Tetration af et tal ved n betyder at eksponentisere det n gange at producere et tårn af magter n historier højt.

Det er svært at sætte hovedet rundt i, hvor hurtigt tetration kommer ud af hånden: $latex 2 uparrowuparrow 3$, eller $latex 2^{2^2}$, er 16, $latex 2 uparrowuparrow 4$ er lidt over 65,000, og $latex 2 uparrowuparrow 5$ er et tal med næsten 20,000 cifre. Det er fysisk umuligt at nedskrive alle cifrene i $latex 2 uparrowuparrow 6$ — en forpligtelse ved at leve i så lille et univers.

I deres skelsættende resultat beviste Czerwiński og hans kolleger, at der eksisterer vektoradditionssystemer af størrelse n hvor den bedste måde at bestemme tilgængelighed på er at kortlægge en sti, der involverer mere end $latex 2 uparrowuparrow n$ overgange, hvilket antyder en ny nedre grænse, der dværgede Liptons. Men hvor hovedsnurrende end fortrængning er, var det stadig ikke det sidste ord om problemets kompleksitet.

Til Quinquagintillion and Beyond 

Blot et par måneder efter den chokerende nye nedre grænse for kompleksiteten af ​​VAS tilgængelighed, Leroux og Schmitz presset ned den øvre grænse havde de etableret tre år tidligere, men de nåede ikke helt ned til tetration. I stedet beviste de, at kompleksiteten af ​​tilgængelighedsproblemet ikke kan vokse hurtigere end en matematisk monstrøsitet kaldet Ackermann-funktionen.

For at forstå denne funktion skal du tage det mønster, der blev brugt til at definere tetration, til sin dystre konklusion. Den næste operation i sekvensen, kaldet pentation, repræsenterer gentagen tetration; det efterfølges af endnu en operation (hexation) for gentagen pentation og så videre.

Ackermann-funktionen, betegnet $latex A(n)$, er, hvad du får, når du bevæger dig et trin op ad denne operationsstige med hvert stop på tallinjen: $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}}$, og så videre. Antallet af cifre i $latex A(4)$ er i sig selv et kolossalt tal, der omtrent svarer til 1 quinquagintillion — det er det finurlige og sjældent nødvendige navn for en 1 efterfulgt af 153 nuller. "Du skal ikke bekymre dig om Ackermann på 5," rådede Javier Esparza, en datalog ved det tekniske universitet i München.

Leroux og Schmitz' resultat efterlod et stort hul mellem nedre og øvre grænser - den præcise kompleksitet af VAS-nåbarhedsproblemet kunne ligge i begge ender af området eller hvor som helst derimellem. Czerwiński havde ikke tænkt sig at lade det hul stå. "Vi blev ved med at arbejde på det her, fordi det var klart, at det er den største ting, vi nogensinde har gjort i vores liv," sagde han.

Det endelige gennembrud kom i 2021, mens Czerwiński rådgav en andenårs bachelorstuderende ved navn Łukasz Orlikowski. Han tildelte Orlikowski en simpel variant af problemet for at få ham op at køre, og Orlikowskis arbejde hjalp de to med at udvikle en ny teknik, der også gjaldt det generelle problem med tilgængelighed. Det gjorde det muligt for dem hæve den nedre grænse væsentligt - helt op til Leroux og Schmitz' Ackermann-overgrænse. At arbejde selvstændigt opnåede Leroux et tilsvarende resultat omkring samme tid.

Endelig havde forskere fastlagt den sande kompleksitet af tilgængelighedsproblemet. Czerwiński, Orlikowski og Leroux' nedre grænse viste, at der er en sekvens af progressivt større vektoradditionssystemer, hvor den korteste vej mellem to tilstande vokser i forhold til Ackermann-funktionen. Leroux og Schmitz' øvre grænse viste, at tilgængelighedsproblemet ikke kan blive mere komplekst end det - en lille trøst for enhver, der håber på en ufejlbarlig praktisk procedure til at løse det. Det er en slående illustration af, hvor subtile tilsyneladende simple beregningsproblemer kan være.

Aldrig færdig

Forskere har fortsat med at studere VAS-nåbarhedsproblemet efter at have bestemt dets nøjagtige kompleksitet, da mange varianter af spørgsmålet forbliver ubesvarede. Ackermann øvre og nedre grænser skelner for eksempel ikke mellem de forskellige måder at øge n, såsom at øge dimensionaliteten af ​​vektorerne eller øge antallet af tilladte overgange.

For nylig har Czerwiński og hans kolleger gjort fremskridt at pirre disse særskilte effekter fra hinanden ved at studere, hvor hurtigt kompleksiteten kan stige i varianter af vektoradditionssystemer med fast dimensionalitet. Men mere skal gøres - selv i tre dimensioner, hvor vektoradditionssystemer er nemme at visualisere, forbliver den nøjagtige kompleksitet af tilgængelighedsproblemet ukendt.

"På en måde er det bare pinligt for os," sagde Mazowiecki.

Forskere håber, at en bedre forståelse af relativt simple tilfælde vil hjælpe dem med at udvikle nye værktøjer til at studere andre beregningsmodeller, der er mere komplicerede end vektoradditionssystemer. I øjeblikket ved vi næsten intet om disse mere komplicerede modeller.

"Jeg ser dette som en del af en meget grundlæggende søgen efter at forstå beregningsevne," sagde Zetzsche.

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores datalogisk læserundersøgelse og du vil være med til at vinde gratis Quanta varer.