Geheimnisvoller mathematischer Genie und Schriftsteller fördern die Lösung des Permutationsproblems

Ursprünglicher Autor: Erica Klarreich
  • Übersetzung

Neue Beweise für die Autorschaft des australischen Science-Fiction-Autors Greg Egan und Beweise aus dem Jahr 2011, die anonym im Netzwerk veröffentlicht wurden, wurden als bedeutende Durchbrüche bei der Untersuchung des Rätsels anerkannt, das Mathematiker seit 25 Jahren studieren




Am 16. September 2011 stellte ein Anime-Fan eine mathematische Frage 4chan über die Kult-Fernsehserie Haruni Suzumiyas Melancholie . Die erste Staffel der Show, in der es Zeitreisen gab, wurde in einer anderen als der chronologischen Weise gezeigt, und während der folgenden Show und Veröffentlichung auf DVD wurde die Reihenfolge der Episoden erneut geändert. Im Internet stritten sich die Fans über die Reihenfolge, in der die Serie am besten anzusehen ist, und der Autor der Frage fragte, ob die Zuschauer die Serie auf alle möglichen Arten sehen wollten, wie viele Episoden wären auf ihrer kürzesten Liste? [ Verweis auf eine Liste, in der Sie eine beliebige Folge von Episoden finden können / ca. trans. ]

In weniger als einer Stunde gab ein anonymer Autor die Antwort auf die Frage - keine vollständige Lösung, sondern eine Untergrenze für die erforderliche Anzahl von Episoden. Aus seiner für eine beliebige Anzahl von Episoden geltenden Argumentation folgt, dass der Zuschauer für die erste Staffel von Haruhi, bestehend aus 14 Episoden, mindestens 93.884.313.611 Episoden hintereinander sehen muss, um alle möglichen Permutationen zu studieren. "Untersuchen Sie die Beweise auf Fehler, die ich möglicherweise übersehen hätte", schrieb der Autor.

Der Beweis von sieben Jahren blieb in der mathematischen Gemeinschaft unbemerkt - es stellte sich heraus, dass zu diesem Zeitpunkt nur ein professioneller Mathematiker ihn bemerkte, und er lernte es nicht sorgfältig genug. Aber im letzten Monat hat der australische Science-Fiction-Autor Greg Egan die Existenz eines neuen bewiesendie Obergrenze für die erforderliche Anzahl von Episoden. Die Eröffnung von Egan weckte erneut das Interesse an dem Problem und machte ab 2011 auf die Aufzeichnungen über die untere Grenze aufmerksam. Beide Beweise gelten nun als bedeutende Durchbrüche beim Studium des Rätsels, das Mathematiker seit mindestens 25 Jahren studieren.

Mathematiker überprüften schnell die obere Grenze von Eagan, was ebenso wie die untere Grenze für Sequenzen beliebiger Länge gilt. Robin Houston, ein Mathematiker bei Kiln, ein Unternehmen für Datenvisualisierung, und Jay Panton von der Marquette University, Milwaukee, bestätigten unabhängig die Arbeit eines anonymen Autors mit 4chan. "Es wurde viel Mühe aufgewendet, um die Richtigkeit dieser Hypothese zu überprüfen", sagte Panton, da die Schlüsselideen des Beweises nicht klar ausgedrückt wurden.

Nun haben Houston und Panton zusammen mit Vince Vater von der University of Florida eine formelle Arbeit geschrieben . Darin bezeichneten sie den Erstautor als „anonymes Poster 4chan“.

"Das Seltsame an der Situation ist, dass dieser sehr elegante Beweis einer zuvor unbekannten Tatsache an einem so unwahrscheinlichen Ort erschien", sagte Houston.

Permutationsstädte


Wenn es nur drei Episoden in der Serie gibt, gibt es sechs Möglichkeiten, sie anzusehen: 123, 132, 213, 231, 312 und 321. Sie können sie zusammenfügen und eine Liste von 18 Episoden erstellen, die jede Reihenfolge enthalten. Es gibt jedoch auch einen effizienteren Weg zum Verkleben: 123121321. Eine solche Sequenz, die alle Permutationen einer Menge von n Zeichen enthält, wird Superpermutation genannt.

1993 fanden Daniel Ashlok und Janet Tilotson, dass bei der Untersuchung der kürzesten Superpermutationen für verschiedene n-Werte schnell faktorielle Faktoren auftreten - dieselben Werte, die als n! Geschrieben werden, dh alle Zahlen von 1 bis n multiplizieren (z. B. 4) ! = 4 * 3 * 2 * 1).

Wenn Ihre Serie nur 1 Episode enthält, beträgt die Länge der kürzesten Superpermutation 1! (auch bekannt als die gute alte Einheit). Bei einer Folge mit zwei Folgen hat die kürzeste Superpermutation (121) eine Länge von 2! + 1! .. Für drei Episoden (Beispiel oben) ist die Länge gleich 3! + 2! + 1! Und für vier Folgen (123412314231243121342132413214321) wird es 4 sein! + 3! + 2! + 1! .. Regel factorials allgemein akzeptiert (obwohl niemand beweisen konnte , dass es für alle n wahr ist), und bestätigte später seine Mathematik für n = 5.

Dann, im Jahr 2014 getroffen Houston Mathematiker zeigtfür n = 6 funktioniert die Regel nicht mehr. Die Regel sagt voraus, dass die Betrachtung von sechs Episoden auf alle möglichen Arten 873 Episoden erfordern würde, aber Houston fand 872 einen Weg, es zu tun Fakultäten funktionieren nicht für alle n> 6.

Building Houston wandelt das Problem der Superpermutation in das berühmte Problem des reisenden Verkäufers um, das den kürzesten Weg durch mehrere Städte sucht. Superpermutationen sind insbesondere mit der "asymmetrischen" Aufgabe des reisenden Verkäufers verbunden, bei der jeder Weg zwischen den beiden Städten seinen Preis hat (nicht notwendigerweise in beiden Richtungen gleich), und das Ziel besteht darin, den günstigsten Weg durch alle Städte zu finden.

Diese Transformation ist leicht zu verstehen: Stellen Sie sich vor, dass jede Permutation eine Stadt ist, und stellen Sie sich den Weg von jeder Permutation zur jeweils anderen Permutation vor. Beim Superpermutationsproblem benötigen wir die kürzeste Ziffernfolge, in der alle Permutationen vorhanden sind. Daher ist es unser Ziel, alle Permutationen zu durchlaufen, um der ursprünglichen Permutation so wenige Zahlen wie möglich hinzuzufügen. Wir erklären, dass die Kosten für jeden Pfad einfach gleich der Anzahl von Ziffern sind, die wir an das Ende der ersten Permutation anhängen müssen, um die zweite zu erhalten. In dem Beispiel mit n = 3 kostet der Pfad von 231 nach 312 $ 1, da wir nur 2 zum Ende von 231 addieren müssen, um 312 zu erhalten, und der Pfad von 231 nach 132 $ 2 kostet, da wir 32 hinzufügen müssen. In einer solchen Formulierung ist der billigste Weg durch Alle Städte entsprechen direkt der kürzesten Superpermutation.



Aufgrund dieser Umwandlung konnte Houston alle Fähigkeiten der Algorithmen zur Lösung des Problems des reisenden Verkäufers auf das Problem der Superpermutation lenken. Diese Aufgabe ist für ihre Zugehörigkeit zur Klasse NP-Komplex bekannt, was bedeutet, dass es keinen effektiven Algorithmus gibt, der ihn im allgemeinen Fall lösen kann. Es gibt jedoch Algorithmen, die einige Arten von Problemen effektiv lösen können, und andere Algorithmen können gute Näherungslösungen liefern. Houston verwendete eine der letzteren, um eine Superpermutation mit einer Länge von 872 Ziffern zu erzeugen.

Da er nur eine ungefähre Lösung gab, ist dies möglicherweise nicht die idealste Superpermutation. Die Mathematiker führen nun eine 3D-Suche nach der kürzesten Super-Permutation mit 6 Zeichen durch, sagte Panton. "Wir wissen, dass unsere Suche in einer begrenzten Zeit endet, aber wir wissen nicht, ob es eine Woche oder eine Million Jahre dauern wird", sagte er. "Es gibt keine Fortschrittsanzeige."

Falsche Reihenfolge


Zu der Zeit, als Houston zur Arbeit kam, saß seit fast drei Jahren ein anonymer Posten bei 4chan in seiner Ecke des Internets. Ein Mathematiker, Nathaniel Johnston von der Mount Ellison University, bemerkte einige Tage nach Erscheinen dieses Eintrags auf einer anderen Website eine Kopie dieses Postens - nicht weil er ein Anime-Liebhaber war, sondern weil er verschiedene Anfragen bei Google eingegeben hatte. mit Superpermutationen verbunden.

Johnston las die Beweise und es schien ihm zuverlässig, aber er verschwendete keine Energie für eine gründliche Überprüfung. Zu dieser Zeit glaubten die Mathematiker, dass die faktorielle Formel für Superpermutationen höchstwahrscheinlich korrekt war. Wenn Sie der Meinung sind, dass Sie die genaue Antwort auf die Frage kennen, ist die untere Grenze der Schätzung für Sie wenig interessant. Mit anderen Worten, die Episoden der Serie über Superpermutationen verliefen in der falschen Reihenfolge.

Danach erwähnte Johnston eine untere Grenze auf einigen Websites , aber "Ich glaube nicht, dass jemand diesem Thema besondere Aufmerksamkeit schenkte", sagte er.

Am 26. September 2018 twitterte der Mathematiker John Baez von der University of California in Riverside einen Beitrag über die Eröffnung von Houston aus dem Jahr 2014 als Teil einer Reihe von Tweets über offensichtliche mathematische Muster, die aufhören zu arbeiten.

Hinweis Trans .: Es gab keine so große Serie von Tweets, nur drei. Die anderen beiden sind auch an sich interessant, obwohl sie nicht mit diesem Artikel verwandt sind. Man sagt, 6 ist die beliebteste Entfernung zwischen zwei benachbarten Primzahlen für alle Primzahlen von weniger als 17.427.000.000.000.000.000.000.000, und dann hört dieses Muster plötzlich auf zu arbeiten! Der zweite demonstriert die folgende Verbindung von Integralen, trigonometrischen Funktionen und der Zahl π.



Aber nur für n <9,8 × 10 42 !


Sein Tweet erregte die Aufmerksamkeit von Egan, der vor einigen Jahrzehnten Mathematik studierte, bevor seine Karriere als anerkannter Science-Fiction-Autor begann (seine erste erfolgreiche Geschichte wurde durch glücklichen Zufall als "Stadt der Permutationen" bezeichnet). "Ich habe nie aufgehört, sich für Mathematik zu interessieren", schrieb Egan per Post.

Egan fragte sich, ob es möglich war, eine noch kürzere Superpermutation als die von Houston zu schaffen. Er beschäftigte sich mit dem Studium der Literatur, wie man Verknüpfungen in den Netzwerken von Permutationen herstellt, und nach einigen Wochen fand er, was er brauchte. Für ein paar Tage leitete er eine neue Obergrenze für die Länge der kürzesten Superpermutation von n Zeichen: n! + (n - 1)! + (n - 2)! + (n - 3)! + n - 3. Sie ähnelt der Faktorialformel, von der viele Mitglieder ausgeschlossen werden.

"Es hat die vorherige Obergrenze völlig überschritten", sagte Houston.

Die Untergrenze des Autors des Posts auf 4chan lag verführerisch nahe der neuen Obergrenze: n! + (n - 1)! + (n - 2)! + n - 3. Nachdem das Ergebnis veröffentlicht worden war, erinnerte Egan Johnston die Mathematiker an den Beweis eines anonymen Autors, und Houston mit Panton bewies bald seine Richtigkeit. Wie in der Arbeit von Houston nähern sich die neuen Unter- und Obergrenzen dem Gesichtspunkt des Problems des reisenden Verkäufers der Superpermutation an: Die Untergrenze zeigt, dass der Weg durch alle Städte eine Mindestanzahl von Pfaden im Wert von mehr als 1 $ durchlaufen muss, und die Obergrenze schafft einen speziellen Weg für jedes n, Verwenden Sie nur Verbindungen im Wert von 1 $ und 2 $.

Nun versuchen die Forscher, die obere und die untere Grenze zusammenzubringen und eine einzige Formel zu finden, die das Problem der Superpermutation löst. "Wahrscheinlich werden die Leute dieses Rätsel am Ende noch lösen", sagte Baez. "Jetzt sieht alles gut aus."

Für Haruhi-Fans gibt Egans Lösung mit einer Gesamtzahl von 93.924.230.411 genaue Anweisungen zur Anzeige aller möglichen Optionen für die Reihenfolge der ersten Staffel: Sie können heute mit dem Browsen beginnen oder warten, bis die Mathematiker diese Zahl noch verringern können. Die untere Grenze eines anonymen Autors beweist, dass diese Kürzungen nicht mehr als 40 Millionen Folgen einsparen - dies reicht jedoch aus, um sich auf die zweite Staffel vorzubereiten.

Jetzt auch beliebt: