ИИ и программист улучшили формулу суперпермутации, сократив количество эпизодов для просмотра на 1

Superpermutation: KI liefert neue Einsichten beim Anime-Problem aus 4chan »Angenommen, eine Fernsehserie hat n Episoden. Du möchtest sie in jeder möglichen Reihenfolge sehen. Wie viele Episoden musst du dir dafür mindestens anschauen?« Diese harmlos anmutende Frage wurde im Jahr 2011 auf dem Imageboard 4chan gestellt. Den Nutzern war vermutlich nicht klar, dass es sich hierbei um ein notorisch komplexes Problem der Kombinatorik handelt, an dem sich Fachleute seit Jahrzehnten die Zähne ausbeißen: die Bestimmung der kürzesten Superpermutation. Erstaunlicherweise lieferte einer der anonymen 4chan-User eine Abschätzung für die Mindestmenge aller zu sehenden Episoden ab, die Mathematikern und Mathematikerinnen bisher nicht bekannt war. Dies wurde zu einer der ikonischsten Nerd-Geschichten. Denn eine genaue Antwort auf diese Frage kennen Fachleute nur, wenn n höchstens fünf ist – für alle weiteren Fälle gibt es nur eine Abschätzung, die der Science-Fiction-Autor Greg Egan im Jahr 2019 veröffentlicht hat. Nun haben ein Softwareentwickler und das Sprachmodell GPT-5.6-Sol gleich drei neue Resultate hervorgebracht, die Egans Ergebnis für n = 8, 9 und 10 übertreffen. Experten vermuten, dass sich diese Resultate verallgemeinern lassen und zu einer besseren Abschätzung für allgemeine n führen könnten. Vom Anime zur Grundlagenforschung Die Diskussion um die Superpermutationen entsprang dem 4chan-Forum zur Anime-Serie »Die Melancholie der Haruhi Suzumiya«. Die erste Staffel der Serie besteht aus 14 Episoden, die man in jeder beliebigen Reihenfolge ansehen kann (ähnlich wie beim achtteiligen Netflix-Thriller »Kaleidoskop«). Und so fragte ein User, wie viele Folgen er mindestens schauen müsse, um die Serie in jeder beliebigen Reihenfolge gesehen zu haben. 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, braucht man Superpermutationen: 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 in diesem Fall zweimal hintereinander die zweite Folge. Eine kürzere Superpermutation wäre daher 1-2-1. Falls eine Serie aus drei Episoden besteht, wird es schon schwieriger, die kürzeste Superpermutation zu finden. Es gibt nämlich 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 durch eine geschickte Wahl der Abfolge eine Abkürzung finden. Die kürzeste Superpermutation ist in diesem Fall: 1-2-3-1-2-1-3-2-1, man muss folglich 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. Keine exakte Lösung mehr bekannt Deshalb müssen sich Fachleute mit Abschätzungen begnügen. Diese enthalten zwar 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, die der kürzesten Superpermutation entspricht. Deshalb war die Formel für die Mindestlänge einer Superpermutation, die der 4chan-User im Jahr 2011 gefunden hatte, aus fachlicher Sicht so bedeutend. Der australische Science-Fiction-Autor Greg Egan hingegen berechnete eine Maximallänge für die kürzesten Superpermutationen. Damit war klar: Will man alle Folgen einer n-teiligen Serie in allen möglichen Kombinationen ansehen, muss man mindestens 𝑛!+(𝑛−1)!+(𝑛−2)!+𝑛−3 Folgen anschauen und höchstens 𝑛!+(𝑛−1)!+(𝑛−2)!+(𝑛−3)!+𝑛−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. Doch Forschenden war klar, dass der Maximalwert von Egan nicht dem Optimum entspricht. Bereits 2019 fand man Beispiele für Superpermutationen von n = 7, die kürzer sind als Egans Abschätzung. Daher fragten sich Fachleute, ob es ähnliche Beispiele für größere Werte von n gibt. Sprich: Lässt sich eine Superpermutation für n größer als sieben finden, die kürzer ist, als Evans Formel angibt? Ende Juli 2026 konnte der Softwareentwickler Uku Raudvere diese Frage bejahen, indem er eine Superpermutation von n = 8 angab, die nur 46 204 statt der von Evans Formel vorhergesagten 46 205 Terme enthält. Am selben Tag meldete sich der Mathematiker William Echols und schrieb in einem Austauschforum: »Ich wollte herausfinden, ob GPT-5.6 in der Lage ist, die Obergrenzen für andere n zu verbessern. In einer etwa zweistündigen Sitzung mit GPT-5.6 in Codex erhielt ich eine Superpermutation der Länge 408 965 für n = 9 und eine Superpermutation der Länge 4 037 046 für n = 10. Interessanterweise sind beide um 1 kürzer als Egans allgemeine Konstruktion.« Nun versuchen die Fachleute, die Methoden der KI und von Raudvere im Detail nachzuvollziehen, in der Hoffnung, dass sie sich verallgemeinern lassen. »Das könnte uns eine verbesserte Abschätzung liefern, die wir schon lange vermutet haben«, schrieb der Kombinatoriker Robin Houston in dem Forum.