Een gemakkelijk klinkend probleem levert getallen op die te groot zijn voor ons universum | Quanta-tijdschrift

Het komt niet vaak voor dat vijfjarigen vragen op het gebied van de informatica kunnen begrijpen, maar het kan gebeuren. Stel bijvoorbeeld dat een kleuter genaamd Alice twee appels heeft, maar zij geeft de voorkeur aan sinaasappels. Gelukkig hebben haar klasgenoten een gezond fruithandelssysteem ontwikkeld met strikt gehandhaafde wisselkoersen: geef bijvoorbeeld een appel op en je kunt een banaan krijgen. Kan Alice een reeks transacties uitvoeren, door bananen of meloenen op te rapen en te lossen, waardoor ze bij haar favoriete fruit komt?

Het klinkt eenvoudig genoeg. “Je kunt naar de basisschool gaan en het aan kinderen vertellen”, zei hij Christoph Haase, een computerwetenschapper aan de Universiteit van Oxford. “Mensen zullen denken: ‘Dat moet wel makkelijk zijn.’”

Maar het wiskundige probleem dat ten grondslag ligt aan het dilemma van Alice – het bereikbaarheidsprobleem voor vectoroptellingssystemen genoemd – is verrassend subtiel. Hoewel sommige gevallen gemakkelijk kunnen worden opgelost, hebben computerwetenschappers bijna een halve eeuw lang geworsteld om een ​​alomvattend begrip van het probleem te ontwikkelen. Nu hebben ze in een reeks doorbraken van de afgelopen jaren duidelijk vastgesteld hoe complex dat probleem precies kan worden.

Het blijkt dat dit kinderlijke probleem absurd, bijna tekenfilmachtig complex is – zo complex als vrijwel alle andere beroemde harde rekenproblemen ziet eruit als, nou ja, kinderspel. Probeer de moeite te kwantificeren die nodig is om dit probleem op te lossen, en al snel zul je te maken krijgen met getallen die zo groot zijn dat je zelfs door de cijfers te tellen naar getallen kunt grijpen waar je nog nooit van hebt gehoord. Dergelijke cijfers nodigen vaak uit tot vergelijkingen met de schaal van het universum, maar zelfs die analogieën schieten tekort. ‘Dat zou het geen recht doen’, zei hij Georg Zetzsche, een computerwetenschapper aan het Max Planck Instituut voor Softwaresystemen in Kaiserslautern, Duitsland. “Het heelal is zo klein.”

Binnen bereik?

Gestript tot de essentie gaat het bereikbaarheidsprobleem over wiskundige objecten die vectoren worden genoemd en die geordende lijsten met getallen zijn. De vermeldingen in deze lijsten worden componenten genoemd, en het aantal componenten in een vector wordt de dimensionaliteit ervan genoemd. De fruitinventaris van Alice kan bijvoorbeeld worden beschreven door een vierdimensionale vector (a, b, c, d), waarvan de componenten aangeven hoeveel appels, bananen, meloenen en sinaasappels ze op een bepaald moment heeft.

Een vectoroptellingssysteem, of VAS, is een verzameling vectoren die de mogelijke overgangen tussen toestanden in een systeem vertegenwoordigen. Voor Alice zou de overgangsvector (−1, −1, 1, 0) de uitwisseling van een appel en een banaan voor een meloen vertegenwoordigen. Het VAS-bereikbaarheidsprobleem vraagt ​​zich af of er een combinatie van toegestane overgangen bestaat die je van een specifieke begintoestand naar een specifieke doeltoestand kan brengen - of, in wiskundige termen, of er een som van overgangsvectoren bestaat die de startvector in de doelvector transformeert. Er is slechts één probleem: geen enkel onderdeel van de vector die de toestand van het systeem beschrijft, kan ooit onder nul komen.

"Dat is een heel natuurlijke beperking voor een model van de werkelijkheid", zei hij Wojciech Czerwiński, een computerwetenschapper aan de Universiteit van Warschau. “Je kunt geen negatief aantal appels hebben.”

In sommige systemen is het eenvoudig om te bepalen of de doelvector bereikbaar is. Maar dat is niet altijd het geval. Computerwetenschappers zijn het meest geïnteresseerd in eenvoudig ogende vectoroptelsystemen waarbij het niet duidelijk is hoe moeilijk het is om de bereikbaarheid te bepalen. Om deze gevallen te bestuderen, beginnen onderzoekers met het definiëren van een getal dat de omvang van een bepaald systeem kwantificeert. Dit nummer, vertegenwoordigd door n, omvat het aantal dimensies, het aantal overgangen en andere factoren. Vervolgens vragen ze hoe snel de moeilijkheidsgraad van het bereikbaarheidsprobleem kan toenemen n wordt groter.

Om die vraag te beantwoorden, gebruiken onderzoekers twee complementaire benaderingen. Ten eerste zoeken ze naar voorbeelden van bijzonder lastige vectoroptelsystemen waarbij het bepalen van de bereikbaarheid een minimale inspanning vergt. Deze minimumniveaus worden ‘ondergrenzen’ genoemd voor de complexiteit van het probleem – ze zeggen tegen onderzoekers: ‘De lastigste systemen voor een gegeven n zijn minstens zo moeilijk.”

Ten tweede proberen onderzoekers ‘bovengrenzen’ vast te stellen – grenzen aan hoe moeilijk bereikbaarheid kan zijn, zelfs in de meest duivelse systemen. Deze zeggen: “De lastigste gevallen voor een gegeven n zijn hooguit zo moeilijk.” Om precies te bepalen hoe moeilijk bereikbaarheid is in de lastigste systemen, proberen onderzoekers de ondergrens omhoog en de bovengrens omlaag te duwen totdat ze elkaar ontmoeten.

Het spul van nachtmerries

Vectortoevoegsystemen hebben een lange geschiedenis. Sinds de jaren zestig hebben computerwetenschappers ze gebruikt om programma's te modelleren die een berekening in veel kleine stukjes opdelen en tegelijkertijd aan die stukjes werken. Dit soort 'concurrent computing' is nu alomtegenwoordig, maar onderzoekers begrijpen de wiskundige grondslagen ervan nog steeds niet volledig.

In 1976, de computerwetenschapper Richard Lipton zette de eerste stap naar het begrijpen van de complexiteit van het VAS-bereikbaarheidsprobleem. Hij ontwikkelde een procedure voor het construeren van systemen waarbij de snelste manier om te bepalen of de ene toestand vanuit de andere bereikbaar is, is door een reeks overgangen daartussen in kaart te brengen. Hierdoor kon hij de lengte van het kortste pad tussen twee zorgvuldig gekozen toestanden gebruiken als maatstaf voor de moeilijkheidsgraad van het bereikbaarheidsprobleem.

Lipton dus bewezen hij zou een systeem van grootte kunnen construeren n waarin het kortste pad tussen twee toestanden meer dan $latex 2^{2^n}$ overgangen omvatte. Dat impliceerde een overeenkomstige dubbele exponentiële ondergrens voor de inspanning die nodig was om de bereikbaarheid in zijn systemen te bepalen. Het was een verrassende ontdekking: dubbele exponentiële groei is het onderwerp van de nachtmerries van computerwetenschappers. Onderzoekers zijn zelfs vaak huiverig voor gewone exponentiële groei, die in vergelijking verbleekt: $latex {2^5}= 32$, maar $latex 2^{2^5}$ is meer dan 4 miljard.

De meeste onderzoekers dachten dat Lipton de meest complexe mogelijke vectortoevoegingssystemen had bedacht, wat betekende dat hij de ondergrens zo hoog mogelijk had verhoogd. Het enige wat in dat geval zou ontbreken, zou een daarbij behorende bovengrens zijn – dat wil zeggen een bewijs dat er geen systeem zou kunnen zijn waarin het bepalen van de bereikbaarheid nog moeilijker zou zijn. Maar niemand wist hoe dat te bewijzen. De computerwetenschapper Ernst Mayr kwam het dichtst in de buurt toen hij bewezen in 1981 dat het in principe altijd mogelijk is om de bereikbaarheid in elk vectoroptellingssysteem te bepalen. Maar zijn bewijs stelde geen kwantitatieve bovengrens aan hoe moeilijk het probleem zou kunnen zijn. Er was een vloer, maar er was geen plafond te zien.

"Ik heb er zeker af en toe over nagedacht", zei Lipton. “Maar na een tijdje gaf ik het op, en voor zover ik kon zien, heeft niemand gedurende veertig jaar enige vooruitgang geboekt.”

In 2015 hebben de computerwetenschappers Jérôme Leroux en Sylvain Schmitz eindelijk gevestigd een kwantitatieve bovengrens – één zo hoog dat onderzoekers aannamen dat het slechts een eerste stap was die naar beneden kon worden gezet om aan de ondergrens van Lipton te voldoen.

Maar dat is niet wat er gebeurde. In 2019 ontdekten onderzoekers een ondergrens die veel hoger was dan die van Lipton, waardoor decennia van conventionele wijsheid op zijn kop werden gezet. Het VAS-bereikbaarheidsprobleem was veel complexer dan iedereen had verwacht.

Een toren van machten

Het schokkende resultaat van 2019 kwam voort uit een mislukking. In 2018 weerlegde Czerwiński een vermoeden van Leroux en Filip Mazowiecki, een computerwetenschapper die nu aan de Universiteit van Warschau werkt, die zou hebben geholpen vooruitgang te boeken bij een gerelateerd probleem. In daaropvolgende discussies stuitten de onderzoekers op een veelbelovende nieuwe manier om extra complexe vectoroptellingsystemen te construeren, wat een nieuwe ondergrens zou kunnen impliceren voor het VAS-bereikbaarheidsprobleem, waar de vooruitgang zo lang tot stilstand was gekomen.

“Alles in mijn hoofd had te maken met de bereikbaarheid van VAS”, herinnert Czerwiński zich. Tijdens een semester met een lichte onderwijslast besloot hij zich uitsluitend op dat probleem te concentreren, samen met Leroux, Mazowiecki en twee andere onderzoekers – Slawomir Lasota van de Universiteit van Warschau en Ranko Lazić van de Universiteit van Warwick.

Na een paar maanden werden hun inspanningen beloond. Czerwiński en zijn collega's gedemonstreerd dat ze systemen voor vectoroptelling konden construeren waarin het kortste pad tussen twee toestanden gerelateerd was aan de grootte van het systeem door een wiskundige operatie genaamd tetratie, waardoor zelfs nachtmerrieachtige dubbele exponentiële groei tam lijkt.

Tetratie is een eenvoudige uitbreiding van een patroon dat de meest bekende bewerkingen in de wiskunde met elkaar verbindt, te beginnen met optellen. Samenvoegen n kopieën van een getal, en het resultaat is gelijk aan het vermenigvuldigen van dat getal met n. Als je je vermenigvuldigt n kopieën van een getal, dat staat gelijk aan machtsverheffing, of het verhogen van het getal naar de ne macht. Tetratie, vaak weergegeven door een paar pijlen die naar boven wijzen, is de volgende stap in deze reeks: een getal tetreren door n betekent het exponentiëren ervan n keer om een ​​toren van krachten te produceren n verhalen hoog.

Het is moeilijk voor te stellen hoe snel tetratie uit de hand loopt: $latex 2 uparrowuparrow 3$, of $latex 2^{2^2}$, is 16, $latex 2 uparrowuparrow 4$ is iets meer dan 65,000, en $latex 2 uparrowuparrow 5$ is een getal met bijna 20,000 cijfers. Het is fysiek onmogelijk om alle cijfers van $latex 2 uparrowuparrow 6$ op te schrijven - een risico dat gepaard gaat met het leven in zo'n klein universum.

Met hun baanbrekende resultaat bewezen Czerwiński en zijn collega's dat er vectoroptellingssystemen van grootte bestaan n waarbij de beste manier om de bereikbaarheid te bepalen bestaat uit het uitstippelen van een pad met meer dan $latex 2 uparrowuparrow n$ overgangen, wat een nieuwe ondergrens impliceert die die van Lipton in de schaduw stelt. Maar hoe duizelingwekkend tetratie ook is, het was nog steeds niet het laatste woord over de complexiteit van het probleem.

Naar Quinquagintillion en verder 

Slechts een paar maanden na de schokkende nieuwe ondergrens over de complexiteit van de VAS-bereikbaarheid, Leroux en Schmitz naar beneden geduwd de bovengrens die ze drie jaar eerder hadden vastgesteld, maar ze bereikten niet helemaal de tetratie. In plaats daarvan bewezen ze dat de complexiteit van het bereikbaarheidsprobleem niet sneller kan groeien dan een wiskundig gedrocht dat de Ackermann-functie wordt genoemd.

Om die functie te begrijpen, moeten we het patroon dat wordt gebruikt om tetratie te definiëren tot het grimmige einde brengen. De volgende bewerking in de reeks, genaamd pentatie, vertegenwoordigt herhaalde tetratie; het wordt gevolgd door nog een andere bewerking (hexation) voor herhaalde pentatie, enzovoort.

De Ackermann-functie, aangeduid als $latex A(n)$, is wat je krijgt als je met elke stop op de getallenlijn één trede hoger op deze ladder van bewerkingen gaat: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 pijl-omhoog 4=4^{4^{4^4}}$, enzovoort. Het aantal cijfers in $latex A(4)$ is zelf een kolossaal getal dat ongeveer gelijk is aan 1 quinquagintiljoen – dat is de grillige en zelden benodigde naam voor een 1 gevolgd door 153 nullen. 'Maak je geen zorgen over Ackermann van 5', adviseerde hij Javier Esparza, een computerwetenschapper aan de Technische Universiteit van München.

Het resultaat van Leroux en Schmitz liet een grote kloof achter tussen de onder- en bovengrenzen; de precieze complexiteit van het VAS-bereikbaarheidsprobleem zou aan beide uiteinden van het bereik kunnen liggen, of ergens daartussenin. Czerwiński was niet van plan dat gat te laten bestaan. "We bleven hieraan werken omdat het duidelijk was dat dit het grootste is wat we ooit in ons leven hebben gedaan", zei hij.

De definitieve doorbraak kwam in 2021, terwijl Czerwiński een tweedejaars student genaamd Łukasz Orlikowski adviseerde. Hij gaf Orlikowski een eenvoudige variant van het probleem om hem op de hoogte te brengen, en het werk van Orlikowski hielp hen samen een nieuwe techniek te ontwikkelen die ook van toepassing was op het algemene bereikbaarheidsprobleem. Dat liet hen toe de ondergrens verhogen substantieel – helemaal tot aan de Ackermann-bovengrens van Leroux en Schmitz. Zelfstandig werkend, behaalde Leroux een gelijkwaardig resultaat rond dezelfde tijd.

Eindelijk hadden onderzoekers de ware complexiteit van het bereikbaarheidsprobleem vastgesteld. De ondergrens van Czerwiński, Orlikowski en Leroux toonde aan dat er een reeks steeds grotere vectoroptellingssystemen bestaat waarin het kortste pad tussen twee toestanden groeit in verhouding tot de Ackermann-functie. De bovengrens van Leroux en Schmitz liet zien dat het bereikbaarheidsprobleem niet complexer kan worden dan dat: weinig troost voor iedereen die hoopt op een onfeilbare praktische procedure om het probleem op te lossen. Het is een treffende illustratie van hoe subtiel ogenschijnlijk eenvoudige rekenproblemen kunnen zijn.

Nooit voltooid

Onderzoekers zijn het VAS-bereikbaarheidsprobleem blijven bestuderen nadat ze de exacte complexiteit ervan hadden vastgesteld, omdat veel varianten van de vraag onbeantwoord blijven. De boven- en ondergrenzen van Ackermann maken bijvoorbeeld geen onderscheid tussen de verschillende manieren van verhogen n, zoals het vergroten van de dimensionaliteit van de vectoren of het vergroten van het aantal toegestane overgangen.

Onlangs hebben Czerwiński en zijn collega's dat gedaan vooruitgang geboekt deze verschillende effecten uit elkaar halen door te bestuderen hoe snel de complexiteit kan toenemen in varianten van vectoroptellingssystemen met vaste dimensionaliteit. Maar er moet nog meer worden gedaan: zelfs in drie dimensies, waar vectoroptellingsystemen gemakkelijk te visualiseren zijn, blijft de exacte complexiteit van het bereikbaarheidsprobleem onbekend.

“In zekere zin is het gewoon gênant voor ons”, zei Mazowiecki.

Onderzoekers hopen dat een beter begrip van relatief eenvoudige gevallen hen zal helpen nieuwe hulpmiddelen te ontwikkelen om andere rekenmodellen te bestuderen die uitgebreider zijn dan systemen voor vectoroptelling. Momenteel weten we vrijwel niets over deze meer uitgebreide modellen.

“Ik beschouw dit als onderdeel van een zeer fundamentele zoektocht om de berekenbaarheid te begrijpen,” zei Zetzsche.

Quanta voert een reeks onderzoeken uit om ons publiek beter van dienst te zijn. Neem onze lezersenquête informatica en je doet mee om gratis te winnen Quanta handelswaar.