In meiner Jugend trieb ich mich häufiger auf Imageboards herum. Dabei handelt es sich um Foren, auf denen anonym Bilder hochgeladen und kommentiert werden. Dort entstanden in den 2000er Jahren die ersten Memes, etwa das »Success Kid«. Eine wichtige Rolle beim Aufkommen solcher Internet-Phänomene spielte das Imageboard 4chan. Unter anderem hat dort das »Rickrolling« seinen Ursprung: Ein User klickt ahnungslos auf einen Link, in der Hoffnung, zu einer bestimmten Seite zu gelangen, und wird stattdessen auf Rick Astleys Lied »Never Gonna Give You Up« geleitet.

Für mich waren Imageboards ein wunderbarer Zeitvertreib, wenn ich mich etwa vor meinen Hausaufgaben oder dem Lernen drücken wollte. Wenn man sich aber auf den richtigen Boards bewegt und etwas Glück hat, kann man wirklich allerlei Wissenswertes erfahren.

Zum Beispiel, wenn man sich 2011 auf 4chan bei einer Diskussion über die Anime-Serie »Die Melancholie der Haruhi Suzumiya« herumtrieb. Die erste Staffel der Serie besteht aus 14 Episoden, die so gestaltet sind, dass man sie in jeder beliebigen Reihenfolge ansehen kann (für Leute, die in der Anime-Welt genauso wenig zu Hause sind wie ich: Auf Netflix gibt es einen achtteiligen Thriller namens »Kaleidoskop«, der demselben Prinzip folgt). Irgendwann fragte jemand, wie viele Folgen er mindestens schauen müsse, um die Serie in jeder beliebigen Reihenfolge gesehen zu haben.

Tatsächlich hängt diese Frage mit so genannten Superpermutationen zusammen. Und wie sich herausstellt, hält dieser mathematische Bereich viele Rätsel bereit: Bis heute können Mathematikerinnen und Mathematiker die obige Frage nicht beantworten.

Das war den 4chan-Usern wohl nicht klar. Dort postete jemand die harmlos anmutende Frage:

Und das Erstaunliche: Einer der anonymen User gab in einem Kommentar eine Abschätzung für die Mindestmenge aller zu sehenden Episoden ab, die Mathematikern und Mathematikerinnen bisher nicht bekannt war. »Ich werde das in mehreren Beiträgen ausführen müssen. Bitte prüft nach, ob ich Schlupflöcher übersehen habe«, schrieb der Nutzer und erklärte in mehreren Schritten, wie er auf seine Abschätzung kam. Andere Nutzende griffen dann die genannten Argumente auf und diskutierten darüber – aber außerhalb von 4chan schlug all das keine Wellen. Niemand schien davon Notiz zu nehmen.

Extremes Binge-Watching

In der Mathematik bezeichnet eine Permutation eine Vertauschung zweier Objekte, also wenn man zum Beispiel AB zu BA umordnet. Würde eine Serie aus nur zwei Teilen bestehen, kann man sich entweder zuerst die erste und dann die zweite Episode (1-2) ansehen oder erst die zweite und dann die erste (2-1). Möchte man die Serie in beiden Reihenfolgen anschauen – etwa um herauszufinden, wie sie am meisten Sinn ergibt –, braucht man Superpermutationen. Dabei handelt es sich um eine Aneinanderreihung aller möglicher Permutationen. Ein Beispiel dafür wäre ein Serienabend, bei dem man zuerst die erste und dann die zweite Episode schaut und dann die zweite und anschließend die erste (1-2-2-1). Allerdings sieht man sich dabei zweimal hintereinander die zweite Folge an. Eine kürzere Superpermutation wäre daher 1-2-1. So muss man nur drei Episoden sehen und hat trotzdem jede mögliche Reihenfolge abgedeckt.

Falls eine Serie aus drei Episoden besteht, wird es schon etwas kniffliger, die kürzeste Superpermutation zu finden. In diesem Fall gibt es 3! = 6 verschiedene Reihenfolgen: 1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1. Glücklicherweise muss man aber nicht 3·6 = 18 Teile ansehen, sondern kann wie im vorigen Fall durch eine geschickte Wahl der Abfolge eine Abkürzung finden. Die kürzeste Superpermutation lautet in diesem Fall: 1-2-3-1-2-1-3-2-1; sie enthält bereits alle möglichen Permutationen der Zahlen 1, 2, 3. Man muss sich demnach nur neun Episoden anschauen!

Auch für Serien, die aus n = 4 und n = 5 Folgen bestehen, haben Mathematikerinnen und Mathematiker die kürzesten Superpermutationen berechnet (im ersten Fall muss man 33 Episoden ansehen, im zweiten 153). Darüber hinaus tappen sie allerdings im Dunkeln. Die kürzesten Superpermutationen sind für n größer als 5 nicht bekannt. Tatsächlich hängt die Aufgabe mit einem der hartnäckigsten Probleme der Algorithmik zusammen: dem Problem des Handlungsreisenden.

Dieses handelt von einer Person, die verschiedene Städte besuchen möchte und am Ende wieder in ihrer Heimatstadt landen soll. Aufgabe ist es, den kürzesten Weg zu ermitteln, der alle Städte miteinander verbindet. Im Setting der kürzesten Superpermutation stehen die einzelnen Permutationen für verschiedene Städte. In diesem Fall ordnet man den »Städten« (Permutationen) unterschiedliche »Distanzen« zu, indem man den Überlapp der Permutationen ermittelt. Zum Beispiel haben 1-2-3 und 2-3-1 einen großen Überlapp. Da die letzten beiden Ziffern der ersten Permutation mit den ersten beiden Ziffern der zweiten übereinstimmen, kann man sie zu 1-2-3-1 kombinieren. Deshalb weist man ihnen eine kurze Distanz zu. Hingegen überlappen 1-2-3 und 2-1-3 nicht (um beide Reihenfolgen zu sehen, muss man volle sechs Teile gucken; es ist keine Abkürzung möglich) und haben daher eine große Entfernung zueinander.

Wie beim Problem des Handlungsreisenden versucht man hier, die kürzeste Route innerhalb der Permutationen zu finden. Man verbindet dafür jene Permutationen miteinander, die sich am stärksten überlappen. Es gibt nur eine Schwierigkeit: Es ist kein Algorithmus bekannt, der das Problem des Handlungsreisenden schnell löst. Für wenige Städte, das heißt wenige Episoden n, ist das kein großes Problem. Doch sobald n groß wird, scheitern Computer an der Aufgabe – denn die Rechenzeit wächst exponentiell mit n an.

Auf die richtige Schätzung kommt es an!

Computern gelingt es also noch, das Problem für n = 4 und n = 5 zu lösen; alles darüber hinaus aber nicht mehr. Es ist zwar schon gelungen, Superpermutationen für größere Zahlen zu berechnen, doch bisher ist unklar, ob es nicht noch kürzere gibt.

Deshalb müssen sich Fachleute mit Abschätzungen begnügen. Sie können die Länge der kürzesten Superpermutationen inzwischen ganz gut eingrenzen. Zum Beispiel gibt es einen Algorithmus, der für n Objekte eine Superpermutation aufstellt, die eine Länge von 1! + 2! + 3! + … + n! hat. Für n = 2 erhält man demnach eine Superpermutation der Länge 1 + 2 = 3, was wirklich die kürzeste ist. Für n = 3 folgt eine Länge von 1 + 2 + 6 = 9, für n = 4 erhält man 33, und für n = 5 ergibt sich 153, was in allen drei Fällen der kürzesten Superpermutation entspricht. Für größere n gilt das allerdings nicht mehr: Computer konnten kürzere Superpermutationen finden. Tatsächlich überschätzt die Formel 1! + 2! + 3! + … + n! die Länge der kürzesten Superpermutation für große n massiv.

Solche Annäherungen enthalten nicht die volle Wahrheit. Aber man kann sich durch passende Eingrenzungen dem gesuchten Wert nähern. Fachleute hoffen, den wahren Wert immer weiter einzukesseln, damit er immer weniger Spielraum hat und sich daraus irgendwann eine präzise Zahl berechnen lässt.

Eine Geschichte voller Zufälle und Wiederentdeckungen

Umso bedeutender ist daher die Formel für die Mindestlänge einer Superpermutation, die der 4chan-User im Jahr 2011 gefunden hatte. Dennoch blieb sie knapp drei Jahre lang völlig unbemerkt, bis der Mathematikprofessor Nathaniel Johnston von der Mount Allison University auf einer Fandom-Seite von »Die Melancholie der Haruhi Suzumiya« landete. Johnston selbst war kein Anime-Fan; er gelangte auf die Website, nachdem er einige Suchbegriffe zu Superpermutationen gegoogelt hatte. Dort stieß er auf die Diskussion, die drei Jahre zuvor auf 4chan geführt worden war – ein Nutzer hatte sie auf die Fandom-Seite kopiert.

Später berichtete Johnston, die Erklärung des anonymen 4chan-Users habe plausibel geklungen. Aber er machte sich nicht die Mühe, sie gesondert durchzurechnen, sondern erwähnte das Ergebnis lediglich in einer Randnotiz seines Blogs. Auch diese blieb mehrere Jahre lang unbemerkt.

Erst im Oktober 2018 stieß der Mathematiker Robin Houston auf den Blogpost seines Kollegen – und das nur wegen eines weiteren kuriosen Zufalls. Houston hatte kurz zuvor erfahren, dass der australische Sciencefiction-Autor Greg Egan eine neue Maximallänge für die kürzesten Superpermutationen gefunden hatte:

Das an sich war schon skurril. Doch als Houston anfing, mehr zu diesem Ergebnis in Erfahrung zu bringen, stellte er fest, dass auch die Mindestlänge einer Superpermutation ganz heimlich einen neuen Wert bekommen hatte; und zwar durch einen anonymen Anime-Fandom-Nutzer (er wusste damals noch nichts von dem Ursprung auf 4chan). Die Formel für die Mindestlänge lautet demnach:

Das teilte Houston sogleich auf Twitter, was nun endlich die angemessene Aufmerksamkeit nach sich zog:

Houston beschloss, gemeinsam mit seinen Kollegen Jay Pantone und Vince Vatter den Beweis des 4chan-Nutzers zu überprüfen und auf mathematische Weise aufzuschreiben. Im Oktober 2018 veröffentlichten sie ihre mathematische Arbeit; Erstautor ist aber keiner der drei Mathematiker, sondern: »Anonymous 4chan Poster«.

Damit ist inzwischen klar: Will man alle Folgen einer n-teiligen Serie in allen möglichen Kombinationen ansehen, muss man mindestens \( n! +(n-1)! + (n-2)! +n-3 \) Folgen anschauen und höchstens \( n! +(n-1)! + (n-2)! + (n-3)! +n-3 \). Im Fall der Serie »Kaleidoskop«, die aus acht Folgen besteht, müsste man also mindestens 46 085 Episoden und höchstens 46 205 schauen. Für Haruhi mit 14 Folgen wächst die Anzahl drastisch an. In diesem Fall müsste man mindestens 93 884 313 611 und höchstens 93 924 230 411 Folgen ansehen.

Glücklicherweise hat der Sciencefiction-Autor Egan bei seiner Abschätzung auch einen Algorithmus mitgeliefert, um die entsprechende Superpermutation zu konstruieren. Das heißt, Haruhi-Fans können die Reihenfolge der Anime-Episoden explizit ausrechnen. Bei einer durchschnittlichen Episodenlänge von rund 24 Minuten wäre man mehr als vier Millionen Jahre beschäftigt. Das ist dann vielleicht doch etwas viel Prokrastination. Ich bleibe eher dabei, ein paar Stunden pro Woche auf Imageboards zu verbringen.