Es kommt nicht oft vor, dass 5-Jährige Fragen an den Grenzen der Informatik verstehen können, aber es kann passieren. Nehmen wir zum Beispiel an, dass eine Kindergärtnerin namens Alice zwei Äpfel hat, aber Orangen bevorzugt. Glücklicherweise haben ihre Klassenkameraden ein gesundes Obsthandelssystem mit streng durchgesetzten Wechselkursen entwickelt: Geben Sie beispielsweise einen Apfel auf, und Sie können eine Banane bekommen. Kann Alice eine Reihe von Geschäften ausführen, indem sie Bananen oder Melonen aufnimmt und ablädt, um zu ihrer Lieblingsfrucht zu gelangen?

Es klingt einfach genug. „Sie können in die Grundschule gehen und es den Kindern erzählen“, sagte er Christoph Haase, Informatiker an der Universität Oxford. „Die Leute werden denken: ‚Das muss einfach sein.‘“

Aber das mathematische Problem, das Alices Dilemma zugrunde liegt – das sogenannte Erreichbarkeitsproblem für Vektoradditionssysteme – ist überraschend subtil. Während einige Fälle leicht zu lösen sind, kämpften Informatiker fast ein halbes Jahrhundert lang darum, ein umfassendes Verständnis des Problems zu entwickeln. Nun haben sie in den letzten Jahren durch eine Reihe von Durchbrüchen klar herausgefunden, wie komplex dieses Problem werden kann.

Es stellt sich heraus, dass dieses kindliche Problem absurd, fast karikaturistisch komplex ist – so komplex wie praktisch alle anderen bekanntermaßen schwierige Rechenprobleme sieht aus wie ein Kinderspiel. Versuchen Sie, den zur Lösung dieses Problems erforderlichen Aufwand zu quantifizieren, und schon bald werden Sie mit Zahlen konfrontiert, die so groß sind, dass Sie selbst beim Zählen ihrer Ziffern nach Zahlen greifen, von denen Sie noch nie gehört haben. Solche Zahlen laden oft zu Vergleichen mit der Größe des Universums ein, aber selbst diese Analogien greifen zu kurz. „Das würde dem nicht gerecht werden“, sagte er Georg Zetzsche, Informatiker am Max-Planck-Institut für Softwaresysteme in Kaiserslautern. „Das Universum ist so klein.“

In Reichweite?

Im Kern geht es beim Erreichbarkeitsproblem um mathematische Objekte, sogenannte Vektoren, bei denen es sich um geordnete Zahlenlisten handelt. Die Einträge in diesen Listen werden als Komponenten bezeichnet, und die Anzahl der Komponenten in einem Vektor wird als seine Dimensionalität bezeichnet. Der Fruchtbestand von Alice kann beispielsweise durch einen vierdimensionalen Vektor beschrieben werden (a, b, c, d), deren Bestandteile repräsentieren, wie viele Äpfel, Bananen, Melonen und Orangen sie zu einem bestimmten Zeitpunkt hat.

Ein Vektoradditionssystem oder VAS ist eine Sammlung von Vektoren, die die möglichen Übergänge zwischen Zuständen in einem System darstellen. Für Alice würde der Übergangsvektor (−1, −1, 1, 0) den Austausch eines Apfels und einer Banane gegen eine Melone darstellen. Das VAS-Erreichbarkeitsproblem stellt die Frage, ob es eine Kombination zulässiger Übergänge gibt, die Sie von einem bestimmten Anfangszustand zu einem bestimmten Zielzustand führen können – oder, mathematisch ausgedrückt, ob es eine Summe von Übergangsvektoren gibt, die den Startvektor in den Zielvektor umwandelt. Es gibt nur einen Haken: Keine Komponente des Vektors, der den Systemzustand beschreibt, kann jemals unter Null fallen.

„Das ist eine ganz natürliche Einschränkung für ein Modell der Realität“, sagte er Wojciech Czerwiński, Informatiker an der Universität Warschau. „Man kann keine negative Anzahl an Äpfeln haben.“

In einigen Systemen lässt sich leicht feststellen, ob der Zielvektor erreichbar ist. Aber das ist nicht immer der Fall. Informatiker interessieren sich vor allem für einfach aussehende Vektoradditionssysteme, bei denen nicht offensichtlich ist, wie schwierig es ist, die Erreichbarkeit zu bestimmen. Um diese Fälle zu untersuchen, definieren Forscher zunächst eine Zahl, die die Größe eines bestimmten Systems quantifiziert. Diese Zahl, dargestellt durch numfasst die Anzahl der Dimensionen, die Anzahl der Übergänge und andere Faktoren. Anschließend fragen sie, wie schnell die Schwierigkeit des Erreichbarkeitsproblems zunehmen kann n wird größer.

Um diese Frage zu beantworten, verwenden Forscher zwei komplementäre Ansätze. Zunächst suchen sie nach Beispielen für besonders knifflige Vektoradditionssysteme, bei denen die Bestimmung der Erreichbarkeit einen minimalen Aufwand erfordert. Diese Mindestniveaus werden als „untere Grenzen“ der Komplexität des Problems bezeichnet – sie sagen den Forschern: „Die schwierigsten Systeme für eine gegebene Situation.“ n sind mindestens so schwer.“

Zweitens versuchen Forscher, „Obergrenzen“ festzulegen – Grenzen dafür, wie schwer die Erreichbarkeit selbst in den teuflischsten Systemen möglicherweise werden kann. Diese sagen: „Die schwierigsten Fälle überhaupt.“ n sind höchstens so schwer.“ Um genau zu bestimmen, wie schwer die Erreichbarkeit in den schwierigsten Systemen ist, versuchen Forscher, die Untergrenzen nach oben und die Obergrenzen nach unten zu verschieben, bis sie sich treffen.

Das Zeug der Albträume

Vektoradditionssysteme haben eine lange Geschichte. Seit den 1960er Jahren verwenden Informatiker sie zur Modellierung von Programmen, die eine Berechnung in viele kleine Teile zerlegen und diese Teile gleichzeitig bearbeiten. Diese Art des „Concurrent Computing“ ist mittlerweile allgegenwärtig, aber die Forscher verstehen seine mathematischen Grundlagen immer noch nicht vollständig.

1976 wurde der Informatiker Richard Lipton hat den ersten Schritt zum Verständnis der Komplexität des VAS-Erreichbarkeitsproblems getan. Er entwickelte ein Verfahren zum Aufbau von Systemen, bei dem der schnellste Weg, um festzustellen, ob ein Zustand von einem anderen aus erreichbar ist, darin besteht, eine Abfolge von Übergängen zwischen ihnen abzubilden. Dadurch konnte er die Länge des kürzesten Weges zwischen zwei sorgfältig ausgewählten Staaten als Maß für die Schwierigkeit des Erreichbarkeitsproblems verwenden.

Dann Lipton erwies sich er konnte ein Größensystem konstruieren n bei dem der kürzeste Weg zwischen zwei Zuständen mehr als $latex 2^{2^n}$ Übergänge umfasste. Dies implizierte eine entsprechende doppelte exponentielle Untergrenze für den Aufwand, der zur Bestimmung der Erreichbarkeit in seinen Systemen erforderlich war. Es war eine verblüffende Entdeckung – doppeltes exponentielles Wachstum ist der Stoff, aus dem Informatiker Albträume haben. Tatsächlich schrecken Forscher oft sogar vor einem gewöhnlichen exponentiellen Wachstum zurück, das im Vergleich verblasst: $latex {2^5}= 32$, aber $latex 2^{2^5}$ beträgt über 4 Milliarden.

Die meisten Forscher gingen davon aus, dass Lipton die komplexesten möglichen Vektoradditionssysteme erfunden hatte, was bedeutete, dass er die Untergrenze so hoch wie möglich angehoben hatte. Das einzige, was in diesem Fall fehlte, wäre eine dazugehörige Obergrenze – also ein Beweis dafür, dass es kein System geben könnte, in dem die Bestimmung der Erreichbarkeit noch schwieriger wäre. Aber niemand wusste, wie man das beweisen konnte. Am nächsten kam der Informatiker Ernst Mayr, als er erwies sich 1981, dass es grundsätzlich immer möglich ist, die Erreichbarkeit in jedem Vektoradditionssystem zu bestimmen. Aber sein Beweis legte keine quantitative Obergrenze dafür fest, wie schwierig das Problem sein könnte. Es gab einen Boden, aber keine Decke in Sicht.

„Ich habe auf jeden Fall ab und zu darüber nachgedacht“, sagte Lipton. „Aber nach einer Weile habe ich aufgegeben, und soweit ich das beurteilen konnte, machte schätzungsweise 40 Jahre lang niemand Fortschritte.“

Im Jahr 2015 haben die Informatiker Jérôme Leroux und Sylvain Schmitz endlich etabliert eine quantitative Obergrenze – ein so hoher Wert, dass die Forscher annahmen, es handele sich nur um eine erste Stufe, die nach unten gedrückt werden könnte, um Liptons Untergrenze zu erreichen.

Aber das ist nicht passiert. Im Jahr 2019 entdeckten Forscher eine Untergrenze, die weit über der von Lipton lag, und stellten damit jahrzehntelange gängige Meinungen auf den Kopf. Das Problem der VAS-Erreichbarkeit war weitaus komplexer, als irgendjemand erwartet hatte.

Ein Turm der Mächte

Das schockierende Ergebnis von 2019 entstand aus dem Scheitern. Im Jahr 2018 widerlegte Czerwiński eine Vermutung von Leroux und Filip Mazowiecki, einem Informatiker jetzt an der Universität Warschau, hätte das geholfen, bei einem verwandten Problem Fortschritte zu machen. In den anschließenden Diskussionen stießen die Forscher auf einen vielversprechenden neuen Weg zum Aufbau besonders komplexer Vektoradditionssysteme, der eine neue Untergrenze für das VAS-Erreichbarkeitsproblem bedeuten könnte, bei dem der Fortschritt so lange ins Stocken geraten war.

„Für mich war alles mit der VAS-Erreichbarkeit verbunden“, erinnert sich Czerwiński. Während eines Semesters mit geringer Lehrtätigkeit beschloss er, sich zusammen mit Leroux, Mazowiecki und zwei anderen Forschern ausschließlich diesem Problem zu widmen – Sławomir Lasota der Universität Warschau und Ranko Lazić von der Universität von Warwick.

Nach ein paar Monaten zahlten sich ihre Bemühungen aus. Czerwiński und seine Kollegen weisen nach, dass dass sie Vektoradditionssysteme konstruieren konnten, in denen der kürzeste Weg zwischen zwei Zuständen durch eine mathematische Operation namens Tetration mit der Größe des Systems in Beziehung gesetzt wurde, die selbst das alptraumhafte doppelt exponentielle Wachstum harmlos erscheinen lässt.

Die Tetration ist eine einfache Erweiterung eines Musters, das die bekanntesten Operationen in der Mathematik verbindet, beginnend mit der Addition. Zusammenfügen n Kopien einer Zahl, und das Ergebnis entspricht der Multiplikation dieser Zahl mit n. Wenn man miteinander multipliziert n Kopien einer Zahl, das entspricht einer Potenzierung oder einer Erhöhung der Zahl auf die Zahl ndie Macht. Die Tetration, oft dargestellt durch ein Paar nach oben zeigender Pfeile, ist der nächste Schritt in dieser Sequenz: Tetratieren einer Zahl durch n bedeutet, es zu potenzieren n Zeiten, um einen Turm der Kräfte zu erschaffen n Geschichten hoch.

Man kann sich nur schwer vorstellen, wie schnell die Tetration außer Kontrolle gerät: $latex 2 uparrowuparrow 3$ oder $latex 2^{2^2}$ ist 16, $latex 2 uparrowuparrow 4$ ist etwas über 65,000 und $latex 2 uparrowuparrow 5$ ist eine Zahl mit fast 20,000 Ziffern. Es ist physikalisch unmöglich, alle Ziffern von $latex 2 uparrowuparrow 6$ aufzuschreiben – eine Belastung, die das Leben in einem so kleinen Universum mit sich bringt.

In ihrem bahnbrechenden Ergebnis bewiesen Czerwiński und seine Kollegen, dass es Vektoradditionssysteme der Größe gibt n Dabei lässt sich die Erreichbarkeit am besten bestimmen, indem man einen Pfad mit mehr als $latex 2 uparrowuparrow n$ Übergängen abbildet, was eine neue Untergrenze impliziert, die die von Lipton in den Schatten stellt. Aber so verwirrend die Tetraration auch ist, sie war noch nicht das letzte Wort über die Komplexität des Problems.

Zu Quinquagintillion und darüber hinaus 

Nur wenige Monate nach der schockierenden neuen Untergrenze für die Komplexität der VAS-Erreichbarkeit, Leroux und Schmitz heruntergedrückt Die Obergrenze, die sie drei Jahre zuvor festgelegt hatten, reichte jedoch nicht bis zur Tetratierung. Stattdessen bewiesen sie, dass die Komplexität des Erreichbarkeitsproblems nicht schneller wachsen kann als eine mathematische Monstrosität namens Ackermann-Funktion.

Um diese Funktion zu verstehen, betrachten wir das Muster, das zur Definition der Tetration verwendet wird, bis zu seinem düsteren Ende. Der nächste Vorgang in der Sequenz, Pentation genannt, stellt eine wiederholte Tetration dar; Es folgt eine weitere Operation (Hexation) zur wiederholten Penation und so weiter.

Die Ackermann-Funktion mit der Bezeichnung $latex A(n)$ erhalten Sie, wenn Sie mit jedem Stopp auf der Zahlengeraden eine Stufe auf dieser Operationsleiter nach oben gehen: $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}}$ und so weiter. Die Anzahl der Ziffern in $latex A(4)$ ist selbst eine kolossale Zahl, die ungefähr einer Quinquagintillion entspricht – das ist der skurrile und selten benötigte Name für eine 1 gefolgt von 1 Nullen. „Machen Sie sich keine Sorgen wegen Ackermann von 153“, riet er Javier Esparza, Informatiker an der Technischen Universität München.

Das Ergebnis von Leroux und Schmitz hinterließ eine große Lücke zwischen der Unter- und der Obergrenze – die genaue Komplexität des VAS-Erreichbarkeitsproblems könnte an beiden Enden der Spanne oder irgendwo dazwischen liegen. Czerwiński hatte nicht vor, diese Lücke bestehen zu lassen. „Wir haben weiter daran gearbeitet, weil klar war, dass es das Größte ist, was wir jemals in unserem Leben getan haben“, sagte er.

Der endgültige Durchbruch gelang 2021, als Czerwiński einen Studenten im zweiten Studienjahr namens Łukasz Orlikowski betreute. Er wies Orlikowski eine einfache Variante des Problems zu, um sich auf den neuesten Stand zu bringen, und Orlikowskis Arbeit half den beiden, eine neue Technik zu entwickeln, die auch auf das allgemeine Erreichbarkeitsproblem anwendbar war. Das hat es ihnen ermöglicht Erhöhen Sie die Untergrenze im Wesentlichen – bis zur Ackermann-Obergrenze von Leroux und Schmitz. Leroux arbeitete unabhängig und erhielt ein gleichwertiges Ergebnis um die selbe Zeit.

Schließlich hatten die Forscher die wahre Komplexität des Erreichbarkeitsproblems ermittelt. Die Untergrenze von Czerwiński, Orlikowski und Leroux zeigte, dass es eine Folge immer größerer Vektoradditionssysteme gibt, in denen der kürzeste Weg zwischen zwei Zuständen proportional zur Ackermann-Funktion wächst. Die Obergrenze von Leroux und Schmitz zeigte, dass das Erreichbarkeitsproblem nicht komplexer werden kann – kein Trost für alle, die auf ein unfehlbares praktisches Verfahren zu seiner Lösung hoffen. Es ist ein eindrucksvolles Beispiel dafür, wie subtil scheinbar einfache Rechenprobleme sein können.

Nie fertig

Die Forscher haben das VAS-Erreichbarkeitsproblem weiter untersucht, nachdem sie seine genaue Komplexität ermittelt hatten, da viele Varianten der Frage unbeantwortet bleiben. Die oberen und unteren Ackermann-Grenzen unterscheiden beispielsweise nicht zwischen den verschiedenen Steigerungsarten n, B. die Vergrößerung der Dimensionalität der Vektoren oder die Erhöhung der Anzahl zulässiger Übergänge.

Kürzlich haben Czerwiński und seine Kollegen dies getan Fortschritte gemacht Diese unterschiedlichen Effekte herauszuarbeiten, indem untersucht wird, wie schnell die Komplexität in Varianten von Vektoradditionssystemen mit fester Dimensionalität zunehmen kann. Aber es bleibt noch viel zu tun – selbst in drei Dimensionen, wo Vektoradditionssysteme leicht zu visualisieren sind, bleibt die genaue Komplexität des Erreichbarkeitsproblems unbekannt.

„In gewisser Weise ist es für uns einfach nur peinlich“, sagte Mazowiecki.

Die Forscher hoffen, dass ein besseres Verständnis relativ einfacher Fälle ihnen dabei helfen wird, neue Werkzeuge zu entwickeln, um andere Berechnungsmodelle zu untersuchen, die ausgefeilter sind als Vektoradditionssysteme. Derzeit wissen wir fast nichts über diese aufwändigeren Modelle.

„Ich betrachte dies als Teil einer sehr grundlegenden Suche nach dem Verständnis der Berechenbarkeit“, sagte Zetzsche.

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Informatik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Waren.