Det är inte ofta som 5-åringar kan förstå frågor vid datavetenskapens gränser, men det kan hända. Anta till exempel att en dagisbarn vid namn Alice har två äpplen, men hon föredrar apelsiner. Lyckligtvis har hennes klasskamrater utvecklat ett hälsosamt frukthandelssystem med strikt tvingade växelkurser: Ge upp ett äpple, säg, så kan du få en banan. Kan Alice utföra en serie affärer, genom att plocka upp och lossa bananer eller cantaloupes, som får henne till hennes favoritfrukt?

Det låter enkelt nog. "Du kan gå i grundskolan och berätta [det för] barn," sa Christoph Haase, en datavetare vid University of Oxford. "Folk kommer att tänka, "det måste vara lätt."

Men det matematiska problemet som ligger bakom Alices dilemma – kallat nåbarhetsproblemet för vektoradditionssystem – är förvånansvärt subtilt. Medan vissa fall lätt kan lösas, kämpade datavetare i nästan ett halvt sekel för att utveckla en heltäckande förståelse av problemet. Nu, i en serie av genombrott under de senaste åren, har de fastställt exakt hur komplext det problemet kan bli.

Det visar sig att detta barnsliga problem är absurt, nästan tecknat komplicerat - så komplext att praktiskt taget alla andra kända svåra beräkningsproblem ser ut som en barnlek. Försök att kvantifiera den ansträngning som krävs för att lösa det här problemet, och snart kommer du att möta siffror så stora att även om du räknar deras siffror kommer du att nå siffror du aldrig har hört talas om. Sådana siffror uppmanar ofta till jämförelser med universums skala, men även dessa analogier kommer till korta. "Det skulle inte göra det rättvisa," sa Georg Zetzsche, en datavetare vid Max Planck Institute for Software Systems i Kaiserslautern, Tyskland. "Universum är så litet."

Inom räckhåll?

Avskalat till sin essens handlar nåbarhetsproblemet om matematiska objekt som kallas vektorer, som är ordnade listor med tal. Posterna i dessa listor kallas komponenter, och antalet komponenter i en vektor kallas dess dimensionalitet. Alices fruktinventering, till exempel, kan beskrivas med en fyrdimensionell vektor (a, b, c, d), vars komponenter representerar hur många äpplen, bananer, cantaloupes och apelsiner hon har vid varje given tidpunkt.

Ett vektoradditionssystem, eller VAS, är en samling vektorer som representerar möjliga övergångar mellan tillstånd i ett system. För Alice skulle övergångsvektorn (−1, −1, 1, 0) representera utbytet av ett äpple och en banan mot en cantaloupe. VAS-nåbarhetsproblemet frågar om det finns någon kombination av tillåtna övergångar som kan ta dig från ett specifikt initialtillstånd till ett specifikt måltillstånd – eller, i matematiska termer, om det finns någon summa av övergångsvektorer som omvandlar startvektorn till målvektorn. Det finns bara en hake: Ingen komponent i vektorn som beskriver systemets tillstånd kan någonsin falla under noll.

"Det är en mycket naturlig begränsning för en modell av verkligheten," sa Wojciech Czerwiński, en datavetare vid universitetet i Warszawa. "Du kan inte ha ett negativt antal äpplen."

I vissa system är det lätt att avgöra om målvektorn är nåbar. Men så är det inte alltid. Datavetare är mest intresserade av enkla vektortilläggssystem där det inte är uppenbart hur svårt det är att avgöra tillgängligheten. För att studera dessa fall börjar forskarna med att definiera ett tal som kvantifierar storleken på ett givet system. Detta nummer, representerat av n, omfattar antalet dimensioner, antalet övergångar och andra faktorer. De frågar sedan hur snabbt svårigheten för nåbarhetsproblemet kan öka som n växer sig större.

För att svara på den frågan använder forskarna två kompletterande tillvägagångssätt. Först söker de efter exempel på särskilt knepiga vektoradditionssystem där det krävs en viss minimal ansträngning för att fastställa nåbarhet. Dessa miniminivåer kallas "nedre gränser" för problemets komplexitet - de säger till forskare, "De knepigaste systemen för en given n är åtminstone så här svåra."

För det andra försöker forskare fastställa "övre gränser" - gränser för hur svår nåbarhet kan bli, även i de mest djävulska systemen. Dessa säger, "De svåraste fallen för en given n är på sin höjd så här svåra." För att avgöra exakt hur svårtillgängligheten är i de svåraste systemen, försöker forskare skjuta nedre gränser upp och övre gränser ner tills de möts.

The Stuff of Nightmares

Vektortilläggssystem har en lång historia. Sedan 1960-talet har datavetare använt dem för att modellera program som delar upp en beräkning i många små bitar och arbetar med dessa bitar samtidigt. Denna typ av "samtidig beräkning" är nu allmänt förekommande, men forskare förstår fortfarande inte fullt ut dess matematiska grunder.

1976, datavetaren Richard Lipton tog det första steget mot att förstå komplexiteten i VAS-nåbarhetsproblemet. Han utvecklade en procedur för att konstruera system där det snabbaste sättet att avgöra om ett tillstånd är nåbart från ett annat är att kartlägga en sekvens av övergångar mellan dem. Det gjorde det möjligt för honom att använda längden på den kortaste vägen mellan två noggrant utvalda tillstånd som ett mått på svårigheten med nåbarhetsproblemet.

Lipton då visat han kunde konstruera ett storlekssystem n där den kortaste vägen mellan två tillstånd involverade mer än $latex 2^{2^n}$ övergångar. Det innebar en motsvarande dubbel exponentiell nedre gräns för den ansträngning som krävs för att bestämma nåbarheten i hans system. Det var en häpnadsväckande upptäckt - dubbel exponentiell tillväxt är grejen med datavetares mardrömmar. Faktum är att forskare ofta avskyr även vid vanlig exponentiell tillväxt, som bleknar i jämförelse: $latex {2^5}= 32$, men $latex 2^{2^5}$ är över 4 miljarder.

De flesta forskare trodde att Lipton hade skapat de mest komplexa möjliga vektoradditionssystemen, vilket betyder att han hade höjt den nedre gränsen så högt som den kunde gå. Det enda som saknas i så fall skulle vara en övre gräns för att gå med det - det vill säga ett bevis på att det inte kunde finnas något system där det var ännu svårare att avgöra nåbarhet. Men ingen visste hur man skulle bevisa det. Datavetaren Ernst Mayr kom närmast när han visat 1981 att det i princip alltid är möjligt att bestämma nåbarhet i vilket vektortilläggssystem som helst. Men hans bevis satte ingen kvantitativ övre gräns för hur svårt problemet kunde vara. Det fanns ett golv, men inget tak i sikte.

"Jag tänkte verkligen på det av och på," sa Lipton. "Men efter ett tag gav jag upp, och så vitt jag kunde se gjorde ingen några framsteg på ungefär 40 år."

2015, datavetarna Jérôme Leroux och Sylvain Schmitz äntligen etablerat en kvantitativ övre gräns — en så hög att forskare antog att det bara var ett första steg som kunde tryckas ner för att möta Liptons nedre gräns.

Men det var inte det som hände. Under 2019 upptäckte forskare en lägre gräns som är mycket högre än Liptons, vilket upphäver decennier av konventionell visdom. Problemet med att nå VAS var mycket mer komplext än någon hade räknat med.

Ett makttorn

Det chockerande resultatet 2019 växte fram ur misslyckande. 2018 motbevisade Czerwiński en gissning av Leroux och Filip Mazowiecki, en datavetare nu vid universitetet i Warszawa, som skulle ha hjälpt till att göra framsteg på ett relaterat problem. I efterföljande diskussioner träffade forskarna på ett lovande nytt sätt att konstruera extrakomplexa vektoradditionssystem, vilket kan innebära en ny nedre gräns för VAS-nåbarhetsproblemet, där framstegen hade stannat av så länge.

"Allt kopplade i mitt sinne till VAS-nåbarhet," mindes Czerwiński. Under en termin med lätt undervisningsbelastning bestämde han sig för att enbart fokusera på det problemet, tillsammans med Leroux, Mazowiecki och två andra forskare — Sławomir Lasota vid universitetet i Warszawa och Ranko Lazić av University of Warwick.

Efter några månader gav deras ansträngningar resultat. Czerwiński och hans kollegor demonstreras att de kunde konstruera vektoradditionssystem där den kortaste vägen mellan två tillstånd var relaterad till systemets storlek genom en matematisk operation som kallas tetration som får till och med mardrömslik dubbelexponentiell tillväxt att verka tam.

Tetration är en enkel förlängning av ett mönster som förbinder de mest välbekanta operationerna i matematik, som börjar med addition. Lägg ihop n kopior av ett tal, och resultatet motsvarar att multiplicera det talet med n. Om man multiplicerar tillsammans n kopior av ett tal, som motsvarar exponentiering, eller att höja talet till ne makt. Tetration, ofta representerad av ett par pilar som pekar uppåt, är nästa steg i denna sekvens: Tetration av ett tal med n betyder att exponentiera det n gånger att producera ett torn av makter n berättelser höga.

Det är svårt att omsluta hur snabbt tetration går ur hand: $latex 2 uparrowuparrow 3$, eller $latex 2^{2^2}$, är 16, $latex 2 uparrowuparrow 4$ är drygt 65,000 2, och $latex 5 uparrowuparrow 20,000$ är ett tal med nästan 2 6 siffror. Det är fysiskt omöjligt att skriva ner alla siffror i $latex XNUMX uparrowuparrow XNUMX$ — en skuld för att leva i ett så litet universum.

I sitt landmärkeresultat bevisade Czerwiński och hans kollegor att det finns vektoradditionssystem av storlek n där det bästa sättet att bestämma nåbarhet är att kartlägga en väg som involverar mer än $latex 2 uparrowuparrow n$ övergångar, vilket innebär en ny nedre gräns som dvärgde Liptons. Men hur häftig som tretration än är, det var fortfarande inte det sista ordet om problemets komplexitet.

Till Quinquagintillion and Beyond 

Bara några månader efter den chockerande nya nedre gränsen för komplexiteten i VAS-tillgänglighet, Leroux och Schmitz nedtryckt den övre gränsen hade de fastställt tre år tidigare, men de kom inte hela vägen ner till tetration. Istället visade de att komplexiteten i nåbarhetsproblemet inte kan växa snabbare än en matematisk monstrositet som kallas Ackermann-funktionen.

För att förstå den funktionen, ta mönstret som används för att definiera tetration till dess dystra slutsats. Nästa operation i sekvensen, kallad pentation, representerar upprepad tetration; det följs av ytterligare en operation (hexation) för upprepad pentation och så vidare.

Ackermann-funktionen, betecknad $latex A(n)$, är vad du får när du flyttar ett steg upp på denna stege av operationer med varje stopp på tallinjen: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uppåtpil 4=4^{4^{4^4}}$ och så vidare. Antalet siffror i $latex A(4)$ är i sig ett kolossalt tal ungefär lika med 1 quinquagintillion — det är det nyckfulla och sällan nödvändiga namnet för en 1:a följt av 153 nollor. "Oroa dig inte för Ackermann av 5," rådde Javier Esparza, en datavetare vid Münchens tekniska universitet.

Leroux och Schmitz resultat lämnade ett stort gap mellan nedre och övre gränser - den exakta komplexiteten hos VAS-nåbarhetsproblemet kan ligga i vardera änden av intervallet eller någonstans däremellan. Czerwiński hade inte för avsikt att låta den luckan stå sig. "Vi fortsatte att arbeta med det här eftersom det var uppenbart att det är det största vi någonsin gjort i våra liv," sa han.

Det sista genombrottet kom 2021, medan Czerwiński gav råd till en andraårsstudent vid grundutbildningen Łukasz Orlikowski. Han tilldelade Orlikowski en enkel variant av problemet för att få fart på honom, och Orlikowskis arbete hjälpte de två att utveckla en ny teknik som också gällde det allmänna nåbarhetsproblemet. Det gjorde det möjligt för dem höja den nedre gränsen väsentligen — ända upp till Leroux och Schmitz Ackermann övre gräns. Att arbeta självständigt fick Leroux ett likvärdigt resultat ungefär samma tid.

Slutligen hade forskare fastställt den sanna komplexiteten i nåbarhetsproblemet. Czerwiński, Orlikowski och Leroux nedre gräns visade att det finns en sekvens av progressivt större vektoradditionssystem där den kortaste vägen mellan två tillstånd växer i proportion till Ackermann-funktionen. Leroux och Schmitz övre gräns visade att nåbarhetsproblemet inte kan bli mer komplext än så - liten tröst för alla som hoppas på en ofelbar praktisk procedur för att lösa det. Det är en slående illustration av hur subtila till synes enkla beräkningsproblem kan vara.

Aldrig färdig

Forskare har fortsatt att studera VAS-nåbarhetsproblemet efter att ha bestämt dess exakta komplexitet, eftersom många varianter av frågan förblir obesvarade. Ackermann övre och nedre gränser, till exempel, skiljer inte mellan de olika sätten att öka n, som att öka dimensionaliteten hos vektorerna eller öka antalet tillåtna övergångar.

Nyligen har Czerwiński och hans kollegor gjort framsteg retas isär dessa distinkta effekter genom att studera hur snabbt komplexiteten kan öka i varianter av vektoradditionssystem med fast dimensionalitet. Men mer återstår att göra - även i tre dimensioner, där vektoradditionssystem är lätta att visualisera, är den exakta komplexiteten i nåbarhetsproblemet okänd.

"På ett sätt är det bara pinsamt för oss," sa Mazowiecki.

Forskare hoppas att en bättre förståelse av relativt enkla fall kommer att hjälpa dem att utveckla nya verktyg för att studera andra beräkningsmodeller som är mer utarbetade än vektoradditionssystem. För närvarande vet vi nästan ingenting om dessa mer utarbetade modeller.

"Jag ser detta som en del av en mycket grundläggande strävan att förstå beräkningsbarhet," sa Zetzsche.

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår datavetenskaplig läsarundersökning och du kommer att delta för att vinna gratis Quanta handelsvaror.