Et problem med lett lyd gir tall som er for store for vårt univers | Quanta Magazine

Det er ikke ofte 5-åringer kan forstå spørsmål ved grensene til informatikk, men det kan skje. Tenk deg for eksempel at en barnehagebarn som heter Alice har to epler, men hun foretrekker appelsiner. Heldigvis har klassekameratene hennes utviklet et sunt frukthandelssystem med strengt håndhevede valutakurser: Gi opp et eple, si, og du kan få en banan. Kan Alice utføre en rekke handler, ved å plukke opp og losse bananer eller cantaloupes, som får henne til favorittfrukten hennes?

Det høres enkelt nok ut. "Du kan gå på barneskolen og fortelle [det til] barn," sa Christoph Haase, en informatiker ved University of Oxford. «Folk vil tenke: 'Det må være enkelt.'»

Men det matematiske problemet som ligger til grunn for Alices dilemma – kalt tilgjengelighetsproblemet for vektoraddisjonssystemer – er overraskende subtilt. Mens noen tilfeller kan løses enkelt, kjempet informatikere i nesten et halvt århundre for å utvikle en omfattende forståelse av problemet. Nå, i en rekke gjennombrudd de siste årene, har de fastslått nøyaktig hvor komplekst dette problemet kan bli.

Det viser seg at dette barnlige problemet er absurd, nesten tegneserieaktig komplekst - så komplekst at praktisk talt alle andre kjente vanskelige beregningsproblemer ser ut som en barnelek. Prøv å kvantifisere innsatsen som kreves for å løse dette problemet, og snart vil du møte tall som er så store at selv å telle sifrene deres vil få deg til å strekke deg etter tall du aldri har hørt om. Slike tall inviterer ofte til sammenligninger med universets skala, men selv disse analogiene kommer til kort. "Det ville ikke gjøre det rettferdighet," sa Georg Zetzsche, en informatiker ved Max Planck Institute for Software Systems i Kaiserslautern, Tyskland. "Universet er så lite."

Innenfor rekkevidde?

Strippet til essensen, handler nåbarhetsproblemet om matematiske objekter kalt vektorer, som er ordnede lister med tall. Oppføringene i disse listene kalles komponenter, og antallet komponenter i en vektor kalles dens dimensjonalitet. Alices fruktbeholdning, for eksempel, kan beskrives med en firedimensjonal vektor (a, b, c, d), hvis komponenter representerer hvor mange epler, bananer, cantaloupes og appelsiner hun har til enhver tid.

Et vektoraddisjonssystem, eller VAS, er en samling vektorer som representerer mulige overganger mellom tilstander i et system. For Alice vil overgangsvektoren (−1, −1, 1, 0) representere bytte av et eple og en banan mot en cantaloupe. VAS-tilgjengelighetsproblemet spør om det er en kombinasjon av tillatte overganger som kan ta deg fra en spesifikk starttilstand til en spesifikk måltilstand – eller, i matematiske termer, om det er noen sum av overgangsvektorer som transformerer startvektoren til målvektoren. Det er bare en hake: Ingen komponent i vektoren som beskriver systemets tilstand kan noen gang falle under null.

"Det er en veldig naturlig begrensning for en virkelighetsmodell," sa Wojciech Czerwiński, en informatiker ved universitetet i Warszawa. "Du kan ikke ha et negativt antall epler."

I noen systemer er det enkelt å finne ut om målvektoren er tilgjengelig. Men det er ikke alltid tilfelle. Dataforskere er mest interessert i enkle vektoraddisjonssystemer der det ikke er åpenbart hvor vanskelig det er å bestemme tilgjengelighet. For å studere disse tilfellene starter forskerne med å definere et tall som kvantifiserer størrelsen på et gitt system. Dette tallet, representert ved n, omfatter antall dimensjoner, antall overganger og andre faktorer. De spør deretter hvor raskt vanskeligheten med tilgjengelighetsproblemet kan øke n vokser seg større.

For å svare på det spørsmålet bruker forskerne to komplementære tilnærminger. Først søker de etter eksempler på spesielt vanskelige vektoraddisjonssystemer der bestemmelse av tilgjengelighet krever et minimumsnivå av innsats. Disse minimumsnivåene kalles "nedre grenser" for kompleksiteten til problemet - de sier til forskere, "De vanskeligste systemene for en gitt n er i det minste så vanskelig."

For det andre prøver forskere å etablere "øvre grenser" - grenser for hvor vanskelig tilgjengelighet kan bli, selv i de mest diabolske systemene. Disse sier: "De vanskeligste tilfellene for en gitt n er på det meste så vanskelig.» For å fastslå nøyaktig hvor vanskelig tilgjengeligheten er i de vanskeligste systemene, prøver forskere å skyve nedre grenser opp og øvre grenser ned til de møtes.

The Stuff of Nightmares

Vector addisjonssystemer har en lang historie. Siden 1960-tallet har informatikere brukt dem til å modellere programmer som deler opp en beregning i mange små biter og jobber med disse delene samtidig. Denne typen "samtidig databehandling" er nå allestedsnærværende, men forskere forstår fortsatt ikke fullt ut dets matematiske grunnlag.

I 1976, informatikeren Richard Lipton tok det første skrittet mot å forstå kompleksiteten til VAS-problemet. Han utviklet en prosedyre for å konstruere systemer der den raskeste måten å avgjøre om en tilstand er tilgjengelig fra en annen er å kartlegge en sekvens av overganger mellom dem. Det gjorde det mulig for ham å bruke lengden på den korteste veien mellom to nøye utvalgte tilstander som et mål på vanskelighetsgraden til nåbarhetsproblemet.

Lipton da beviste han kunne konstruere et system av størrelse n der den korteste veien mellom to tilstander involverte mer enn $latex 2^{2^n}$ overganger. Det innebar en tilsvarende dobbel eksponentiell nedre grense for innsatsen som kreves for å bestemme tilgjengelighet i systemene hans. Det var en oppsiktsvekkende oppdagelse - dobbel eksponentiell vekst er innholdet i informatikeres mareritt. Faktisk avviser forskere ofte selv ved vanlig eksponentiell vekst, som blekner i sammenligning: $latex {2^5}= 32$, men $latex 2^{2^5}$ er over 4 milliarder.

De fleste forskere trodde Lipton hadde laget de mest komplekse mulige vektoraddisjonssystemene, noe som betyr at han hadde hevet den nedre grensen så høyt som den kunne gå. Det eneste som mangler, i så fall, ville være en øvre grense for å gå med det - det vil si et bevis på at det ikke kunne være noe system der det var enda vanskeligere å bestemme tilgjengelighet. Men ingen visste hvordan de skulle bevise det. Informatikeren Ernst Mayr kom nærmest da han beviste i 1981 at det i prinsippet alltid er mulig å bestemme tilgjengelighet i et hvilket som helst vektoraddisjonssystem. Men beviset hans satte ingen kvantitativ øvre grense for hvor vanskelig problemet kunne være. Det var et gulv, men ingen tak i sikte.

"Jeg tenkte absolutt på det av og på," sa Lipton. "Men etter en stund ga jeg opp, og så vidt jeg kunne se var det ingen som gjorde noen fremskritt på omtrent 40 år."

I 2015, informatikerne Jérôme Leroux og Sylvain Schmitz endelig etablert en kvantitativ øvre grense - en så høy at forskerne antok at det bare var et første trinn som kunne skyves ned for å møte Liptons nedre grense.

Men det var ikke det som skjedde. I 2019 oppdaget forskere en nedre grense som er langt høyere enn Liptons, noe som øker tiår med konvensjonell visdom. VAS-tilgjengelighetsproblemet var langt mer komplekst enn noen hadde forventet.

Et tårn av makter

Det sjokkerende 2019-resultatet vokste ut av fiasko. I 2018 motbeviste Czerwiński en formodning, av Leroux og Filip Mazowiecki, en informatiker nå ved Universitetet i Warszawa, som ville ha bidratt til å gjøre fremskritt på et relatert problem. I påfølgende diskusjoner traff forskerne en lovende ny måte å konstruere ekstra komplekse vektoraddisjonssystemer, noe som kan innebære en ny nedre grense for VAS-tilgjengelighetsproblemet, der fremgangen hadde stanset så lenge.

"Alt koblet i tankene mine til VAS-tilgjengelighet," husket Czerwiński. I løpet av et semester med lett undervisningsmengde bestemte han seg for å fokusere utelukkende på det problemet, sammen med Leroux, Mazowiecki og to andre forskere - Sławomir Lasota ved universitetet i Warszawa og Ranko Lazić av University of Warwick.

Etter noen måneder ga deres innsats resultater. Czerwiński og hans kolleger demonstrert at de kunne konstruere vektoraddisjonssystemer der den korteste veien mellom to tilstander var relatert til størrelsen på systemet ved en matematisk operasjon kalt tetrering som får til og med marerittaktig dobbel eksponentiell vekst til å virke tam.

Tetrering er en enkel utvidelse av et mønster som forbinder de mest kjente operasjonene i matematikk, som begynner med addisjon. Legg sammen n kopier av et tall, og resultatet tilsvarer å multiplisere det tallet med n. Hvis du multipliserer sammen n kopier av et tall, som tilsvarer eksponentiering, eller heve tallet til nkraften. Tetrering, ofte representert med et par piler som peker oppover, er neste trinn i denne sekvensen: Tetrering av et tall med n betyr å eksponentisere det n ganger for å produsere et tårn av makter n historier høyt.

Det er vanskelig å sette hodet rundt hvor raskt tetration kommer ut av hånden: $latex 2 uparrowuparrow 3$, eller $latex 2^{2^2}$, er 16, $latex 2 uparrowuparrow 4$ er litt over 65,000 2, og $latex 5 uparrowuparrow 20,000$ er et tall med nesten 2 6 sifre. Det er fysisk umulig å skrive ned alle sifrene til $latex XNUMX uparrowuparrow XNUMX$ — en forpliktelse ved å leve i et så lite univers.

I deres landemerkeresultat beviste Czerwiński og hans kolleger at det finnes vektoraddisjonssystemer av størrelse n der den beste måten å bestemme tilgjengelighet på er å kartlegge en bane som involverer mer enn $latex 2 uparrowuparrow n$ overganger, noe som antyder en ny nedre grense som dverget Liptons. Men så hodespinnende som tetration er, var det fortsatt ikke det siste ordet om kompleksiteten til problemet.

Til Quinquagintillion og utover 

Bare noen få måneder etter den sjokkerende nye nedre grensen for kompleksiteten til VAS-tilgjengelighet, Leroux og Schmitz dyttet ned den øvre grensen hadde de etablert tre år tidligere, men de kom ikke helt ned til tetration. I stedet beviste de at kompleksiteten til tilgjengelighetsproblemet ikke kan vokse raskere enn en matematisk monstrositet kalt Ackermann-funksjonen.

For å forstå denne funksjonen, ta mønsteret som ble brukt til å definere tetrasjon til sin dystre konklusjon. Den neste operasjonen i sekvensen, kalt pentasjon, representerer gjentatt tetrasjon; det etterfølges av enda en operasjon (heksering) for gjentatt pentasjon, og så videre.

Ackermann-funksjonen, betegnet $latex A(n)$, er det du får når du går ett trinn opp denne operasjonsstigen med hvert stopp 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. Antall sifre i $latex A(4)$ er i seg selv et kolossalt tall omtrent lik 1 quinquagintillion - det er det lunefulle og sjeldent nødvendige navnet for en 1 etterfulgt av 153 nuller. "Ikke bekymre deg for Ackermann på 5," rådet Javier Esparza, en informatiker ved det tekniske universitetet i München.

Leroux og Schmitz' resultat etterlot et stort gap mellom nedre og øvre grenser - den nøyaktige kompleksiteten til VAS-tilgjengelighetsproblemet kan ligge i hver ende av området eller hvor som helst i mellom. Czerwiński hadde ikke tenkt å la det gapet stå. "Vi fortsatte å jobbe med dette fordi det var klart at det er det største vi noen gang har gjort i våre liv," sa han.

Det endelige gjennombruddet kom i 2021, mens Czerwiński ga råd til en andreårs student ved navn Łukasz Orlikowski. Han tildelte Orlikowski en enkel variant av problemet for å få ham opp i fart, og Orlikowskis arbeid hjalp de to med å utvikle en ny teknikk som også gjaldt det generelle nåbarhetsproblemet. Det gjorde det mulig for dem heve den nedre grensen vesentlig - helt opp til Leroux og Schmitz' Ackermann øvre grense. Arbeider selvstendig, Leroux oppnådd et tilsvarende resultat omtrent på samme tid.

Til slutt hadde forskerne fastslått den sanne kompleksiteten til tilgjengelighetsproblemet. Czerwiński, Orlikowski og Leroux sin nedre grense viste at det er en sekvens av progressivt større vektoraddisjonssystemer der den korteste veien mellom to tilstander vokser i forhold til Ackermann-funksjonen. Leroux og Schmitz' øvre grense viste at nåbarhetsproblemet ikke kan bli mer komplekst enn det - liten trøst for alle som håper på en ufeilbarlig praktisk prosedyre for å løse det. Det er en slående illustrasjon på hvor subtile tilsynelatende enkle beregningsproblemer kan være.

Aldri ferdig

Forskere har fortsatt å studere VAS-tilgjengelighetsproblemet etter å ha bestemt dets eksakte kompleksitet, ettersom mange varianter av spørsmålet forblir ubesvart. Ackermann øvre og nedre grenser, for eksempel, skiller ikke mellom de forskjellige måtene å øke n, som å øke dimensjonaliteten til vektorene eller øke antall tillatte overganger.

Nylig har Czerwiński og hans kolleger gjort fremgang å erte disse distinkte effektene ved å studere hvor raskt kompleksiteten kan øke i varianter av vektoraddisjonssystemer med fast dimensjonalitet. Men mer gjenstår å gjøre - selv i tre dimensjoner, hvor vektoraddisjonssystemer er enkle å visualisere, forblir den nøyaktige kompleksiteten til tilgjengelighetsproblemet ukjent.

"På en måte er det bare pinlig for oss," sa Mazowiecki.

Forskere håper at en bedre forståelse av relativt enkle tilfeller vil hjelpe dem å utvikle nye verktøy for å studere andre beregningsmodeller som er mer forseggjort enn vektoraddisjonssystemer. Foreløpig vet vi nesten ingenting om disse mer forseggjorte modellene.

"Jeg ser på dette som en del av en veldig grunnleggende søken etter å forstå beregnbarhet," sa Zetzsche.

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår informatikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta handelsvarer.