Informatiker nähern sich wichtigem algorithmischen Ziel | Quanta-Magazin

Wenn Sie jemand bittet, festzustellen, ob zwei Objekte gleich sind, mag das wie eine triviale Anfrage erscheinen. In den meisten alltäglichen Fällen reicht ein kurzer Blick aus, um ein genaues Urteil zu fällen.

Aber in der Informatik ist das eine weitaus komplexere Frage. Tatsächlich trifft es den ungeklärten Kern dessen, wozu Computer fähig sind. Je nachdem, um welche Objekte es sich handelt und wie Sie Gleichheit definieren, wissen wir immer noch nicht, ob Computer die Frage schnell beantworten können oder ob ein langsamer und mühsamer Ansatz im Grunde das Beste ist, was sie bewältigen können.

Im letzten Jahrzehnt gab es einige wichtige Ergebnisse, die zeigten, dass Computer zumindest etwas mehr leisten können. Einer der größten aktuellen Ergebnisse In der Informatik gab es einen schnelleren Algorithmus zur Bestimmung, wann zwei Graphen gleich sind. Die Arbeit von 2015, von László Babai von der University of Chicago durchbrach eine wichtige Rechengeschwindigkeitshürde, blieb aber hinter einer anderen zurück.

Nun, ein Artikel von Xiaorui Sun von der University of Illinois, Chicago, hat einen neuen, schnelleren Algorithmus für eine verwandte Frage namens Gruppenisomorphismusproblem vorgestellt, bei der es darum geht zu wissen, wann zwei mathematische Objekte, sogenannte Gruppen, gleich sind. Die Arbeit, online veröffentlicht im vergangenen Märzist ein kleiner Schritt zur Klärung der zugrunde liegenden Rechenkomplexität beim Vergleich von Objekten.

Suns Arbeit durchbricht eine seit langem bestehende Geschwindigkeitsbegrenzung für eine bestimmte Klasse von Gruppen – diejenige, die als das am schwierigsten zu lösende Beispiel des Gruppenisomorphismusproblems gilt. Wenn ein Algorithmus Gruppen dieser Art schnell vergleichen kann, besteht die Hoffnung, dass er auch Gruppen jeglicher Art schnell vergleichen kann.

„Wir kennen einen solchen Satz nicht, aber wir haben Grund zu der Annahme, dass so etwas wahr sein sollte“, sagte er Josch Grochow der University Colorado, Boulder.

Vergleiche vergleichen

Um genau zu bestimmen, ob zwei Dinge gleich sind, müssen Sie zunächst „das Gleiche“ definieren. Zwei Zahlenfolgen könnten als gleich angesehen werden, wenn sie lediglich die gleichen Ziffern enthalten oder wenn sie möglicherweise dieselben Ziffern in derselben Reihenfolge haben müssen.

Isomorphismus ist eine besondere Art von Gleichheit, die in der Mathematik häufig vorkommt. Wenn zwei Objekte zueinander isomorph sind, bedeutet das ungefähr, dass sie dieselben Elemente enthalten und dass diese Elemente in derselben Beziehung zueinander stehen.

Diagramme – Sammlungen von Eckpunkten (Punkten), die durch Kanten (Linien) verbunden sind – bieten eine leicht zugängliche, visuelle Möglichkeit, zu sehen, wie Isomorphismus aussehen kann. Zwei Graphen sind isomorph, wenn Sie Scheitelpunkte in einem Graphen mit Scheitelpunkten in dem anderen vergleichen können, sodass Scheitelpunkte, die im ersten Graphen durch eine Kante verbunden sind, im zweiten durch eine Kante verbunden sind. Isomorphe Graphen können oberflächlich betrachtet unterschiedlich aussehen, sie haben jedoch eine gemeinsame Grundstruktur.

Gruppen sind abstrakter als Diagramme, lassen sich aber dennoch durch Isomorphie vergleichen. Eine Gruppe ist eine Sammlung von Elementen – etwa Zahlen – die nach einer Operation miteinander kombiniert werden können, sodass das Ergebnis auch in der Sammlung enthalten ist. Sie können beispielsweise eine Gruppe haben, deren Elemente die ganzen Zahlen sind – alle positiven und negativen ganzen Zahlen plus Null – und deren Operation die Addition ist: Addieren Sie zwei beliebige ganze Zahlen, und das Ergebnis ist immer eine weitere ganze Zahl.

Zwei Gruppen sind isomorph, wenn Sie jedes Element in einer Gruppe mit einem Element in der anderen koppeln können, sodass das Ergebnis der Operation an zwei Elementen in der ersten Gruppe mit dem Ergebnis der Operation an den äquivalenten Werten dieser Elemente in der zweiten übereinstimmt Gruppe.

Hier ist ein einfaches Beispiel für zwei Gruppen mit jeweils zwei Elementen, die zueinander isomorph sind. Die erste Gruppe besteht aus den Zahlen 0 und 1, die zweite Gruppe aus den Buchstaben a und b. Beide Gruppen enthalten eine Operation zum Kombinieren der Elemente der Gruppe auf eine bestimmte Weise. Die Ergebnisse sind in den folgenden Tabellen aufgeführt.

Die Gruppen sind isomorph, da 0 mit paart a, 1 Paar mit b, und die durch die Kombination von Elementen erzeugte strukturelle Beziehung ist in beiden Gruppen gleich.

„Wir sagen, dass zwei Gruppen isomorph sind, wenn sie grundsätzlich gleichwertig sind“, sagte Sun.

Unausgeglichener Fortschritt

Isomorphismus ist ein wichtiges Konzept in der Mathematik – wo Graphen und Gruppen häufig vorkommen –, weil es Mathematikern ermöglicht, über oberflächliche Unterschiede hinauszuschauen und sich auf die Art und Weise zu konzentrieren, in der verwandte Objekte tatsächlich gleich sein können. Aber auch in der Informatik ist es von grundlegender Bedeutung; Forscher suchen nicht nur nach Algorithmen, die bestimmen, ob zwei Objekte isomorph sind, sondern messen auch, wie schnell diese Algorithmen ausgeführt werden können.

Diese Messung kann schwierig sein. Die Geschwindigkeit eines Algorithmus hängt davon ab, wie sich seine Laufzeit mit der Größe der Objekte ändert, an denen er arbeitet. Stellen Sie sich zum Beispiel vor, Sie haben zwei Gruppenpaare. In einem Paar enthält jede Gruppe fünf Elemente. Im anderen Fall enthält jede Gruppe 10 Elemente.

Man würde erwarten, dass ein Algorithmus mehr Zeit benötigt, um festzustellen, ob die Gruppen mit mehr Elementen isomorph sind. Aber wie viel Zeit noch? Wird es doppelt so lange dauern? 5² länger? 2⁵ länger? Diese Fragen entsprechen wichtigen allgemeinen Klassifizierungen der algorithmischen Geschwindigkeit: Sie können in linearer Zeit (was in diesem Fall bedeutet, dass sie doppelt so lange dauert), polynomialer Zeit (5² länger) und exponentielle Zeit (2⁵ länger).

Informatiker wissen, in welche Geschwindigkeitskategorie die meisten Rechenfragen fallen, aber nicht alle.

„Die meisten sind entweder die einfachsten oder die schwierigsten [Art von Fragen], aber es gibt immer noch einige Ausnahmen, die unbekannt sind“, sagte Sun. Graphen- und Gruppenisomorphie gehören zu diesen Ausnahmen, was ihre Untersuchung so attraktiv macht.

In den 1970s, Robert Tarjan von der Princeton University erkannte, dass es einen Algorithmus gibt, der bestimmen kann, ob zwei beliebige Gruppen mit einer Laufzeit von $latex n^{{(log,n)}}$ isomorph sind, wobei n ist die Anzahl der Elemente in jeder Gruppe. Dies wird als quasi-polynomialer Zeitalgorithmus bezeichnet und ist in der Hierarchie der Laufzeiten besser als die exponentielle Zeit (2ⁿ), aber schlechter als die Polynomzeit (n²). Dies ist ungefähr die gleiche Geschwindigkeit wie Babais Graphisomorphismus-Algorithmus und es ist immer noch das Beste, was wir fast 50 Jahre später für Gruppen erreichen können.

„Das bedeutet ungefähr, dass es seit einem halben Jahrhundert keinen Fortschritt gegeben hat“, sagte Sun.

Zum Zeitpunkt von Tarjans Ergebnis wurde das Gruppenisomorphismusproblem ausführlicher untersucht als die Graphenversion. Das hat sich heute umgekehrt, zum Teil, weil der Graphisomorphismus spannende Innovationen vorangetrieben hat, während der Gruppenisomorphismus ins Stocken geraten ist.

„Alle unsere Tools waren jahrelang sehr langsam und es war schwierig, unser Wissen über die Algebra [von Gruppen] auszunutzen“, sagte er James Wilson der Colorado State University.

Aber trotz dieser Unterschiede im Fortschritt haben die beiden Probleme eine tiefere Verbindung als die Ähnlichkeit ihrer Namen: Das Gruppenisomorphismusproblem (zumindest in dieser Formulierung) reduziert sich auf das Graphisomorphismusproblem. Das bedeutet, dass jeder Algorithmus, der das Graphenproblem lösen kann, in ähnlicher Zeit auch das Gruppenproblem lösen kann. Das Gegenteil ist nicht der Fall – der Fortschritt in der Gruppe bedeutet nicht den Fortschritt in der Grafik. Aber der Mangel an Fortschritten beim Gruppenproblem belastete die Mathematiker, die entsprechende Fortschritte beim Graphenproblem anstrebten. Wie kann man eine schwierigere Sache erreichen, wenn man nicht zuerst etwas erreichen kann, das eng damit zusammenhängt und noch einfacher erscheint?

„Mit anderen Worten“, sagte Sun, „um den Graphisomorphismus weiter zu verbessern, ist der Gruppenisomorphismus ein großer Engpass.“

Ein transformiertes Problem

Wenn der Fortschritt bei einem Problem genauso lange ins Stocken gerät wie bei der Gruppenisomorphie, ist in der Regel Erfindungsreichtum nötig, um aus der Patsche zu kommen. „Wenn es einen großen Fortschritt gibt, sollte das ein Hinweis darauf sein, dass es eine neue Idee gibt“, sagte Grochow.

Suns Arbeit enthält einige Ideen, bei denen es darum geht, einen wichtigen Gruppentyp ins Visier zu nehmen und einen cleveren Weg zu finden, diese Gruppen in Stücke zu zerlegen, um sie zu vergleichen.

Die Gruppen, für die der Sun-Algorithmus arbeitet, werden aufgerufen p-Gruppen der Klasse 2 und Exponent p. Sie ähneln Gruppen, in denen das Produkt zweier Elemente ein anderes Element ist und das Produkt unabhängig von der Reihenfolge, in der Sie sie multiplizieren, gleich bleibt. Aber was wirklich zählt, ist, was sie für das gesamte Gruppenisomorphismusproblem darstellen. Diese Gruppen sind sehr einfach aufgebaut und sollten daher leicht vergleichbar sein. Doch trotz dieser Einfachheit hatten die Forscher keine Möglichkeit gefunden, den Algorithmus zu beschleunigen. Bis sie dazu in der Lage waren, schien es aussichtslos, Verbesserungen an der allgemeinen Frage des Gruppenisomorphismus vorzunehmen.

Sun begann damit, die Einstellung von Gruppen auf Matrizen umzustellen, Zahlenreihen, die als grundlegende Objekte in der linearen Algebra dienen. Möglich wurde dies durch einen Satz aus den 1930er Jahren namens Baer-Korrespondenz, der diese Version der Gruppenisomorphismusfrage in ein vollkommen analoges Problem über Matrizen umwandelt. Insbesondere arbeitete Sun mit Matrixräumen, bei denen es sich um Ansammlungen von Matrizen mit einer besonderen Eigenschaft handelt: Die (lineare) Kombination zweier beliebiger Matrizen im Raum entspricht einer anderen Matrix im Raum.

Mit anderen Worten: Diese Räume sind stark wie Gruppen strukturiert. Anstatt also zu verstehen, wann zwei Gruppen isomorph sind, könnte Sun einfach versuchen zu verstehen, wann zwei Matrixräume isometrisch sind – ein Begriff der Isomorphie von Matrixräumen, der dem von Gruppen entspricht.

Sun war nicht der erste Forscher, der diesen Ansatz übernahm, aber er war der Erste, der einen zusätzlichen Schritt einführte: die Aufteilung eines Matrixraums in zwei Teile. Ein Stück ist der Kern des Raumes, in dem alle Matrizen einfach sind. Der andere Teil ist der Raum um diesen Kern herum, in dem alle Matrizen besonders komplex sind. Dieser Schritt entspricht der Aufteilung einer Gruppe in Untergruppen, die nur einige der gesamten Elemente enthalten.

Anschließend wendete Sun auf jedes dieser Stücke unterschiedliche algorithmische Methoden an. Der Kern hat eine einfache Struktur, daher verwendete er eine Charakterisierung der Struktur, um sie organisierter darzustellen. Die äußere Schicht ist komplexer, daher gibt es keine offensichtlich schnelle Möglichkeit, sie mit einer anderen zu vergleichen. Stattdessen verwendet Suns Methode einen Ansatz namens Individualisierung und Verfeinerung, um die meisten möglichen Möglichkeiten zur Abbildung einer äußeren Schicht auf die andere auszuschließen, und verwendet dann einen Computer, um alle verbleibenden möglichen Wege durchzuarbeiten, um festzustellen, ob eine isomorphe Übereinstimmung vorliegt.

Die Methode ähnelt im Geiste der Lösung eines Sudoku-Rätsels. Es gibt einige Quadrate, deren potenzielle Werte durch das, was Sie bereits wissen (den Kern des Matrixraums), eingeschränkt werden, sodass Sie sie schnell ausfüllen können. Dann gibt es andere (die äußere Schicht), die weniger Einschränkungen haben, die Sie aber herausfinden können, indem Sie alle möglichen Werte ausprobieren – und solange es nicht zu viele solcher Quadrate gibt, können Sie das Rätsel trotzdem lösen eine angemessene Zeitspanne.

„Ich trage alle Dinge ein, von denen ich schnell erkennen kann, dass sie einschränkbar sind, und jetzt gehe ich vielleicht noch einmal hinein und probiere mein Herzblut an den fehlenden Kästchen aus“, sagte Wilson. „Wenn Sie den Bereich eingegrenzt haben, ist es jetzt an der Zeit, den Gang zu wechseln und den Computer für die Suche nach den richtigen Werten zu verwenden.“

Suns Durchbruch zeigte, dass es immer möglich ist, diese Aufteilung für die entsprechenden Matrixräume durchzuführen p-Gruppen der Klasse 2 und Exponent p. Anschließend bewies er, dass nach einer solchen Aufteilung eine Kombination algorithmischer Techniken es ermöglicht, zu bestimmen, ob zwei Räume in $latex n^{{(log,n)}^{5/6}}$ Zeit isomorph sind, ein Wert, der ist etwas niedriger als Tarjans $latex n^{{(log,n)}}$-Methode. (Beide Algorithmen enthalten auch konstante Terme, die keinen großen Einfluss auf die Laufzeit haben und die wir der Übersichtlichkeit halber weggelassen haben.)

Das Ergebnis bestimmt nicht, in welche Geschwindigkeitskategoriegruppen-Isomorphie fällt; es liegt immer noch irgendwo zwischen exponentieller und polynomieller Zeit. Aber Sun hat es etwas näher an die polynomiale Seite der Dinge gerückt, und es gibt Grund zu der Annahme, dass mehr als das möglich sein sollte. Schließlich liefert seine Arbeit Informatikern einen schnelleren Gruppenisomorphismus-Algorithmus für die schwierigsten Gruppenarten, was die Möglichkeit erhöht, dass eine ähnliche Beschleunigung für Gruppen aller Arten in Reichweite sein könnte.

„Wenn du es lösen kannst p-Gruppen, wahrscheinlich können Sie das Ganze lösen“, sagte Grochow. "Vielleicht."