Das Gruppenisomorpieproblem, also die Aufgabe, zu entscheiden, ob zwei gegebene endliche Gruppen isomorph sind, ist eines der fundamentalsten Probleme in der algorithmischen Gruppentheorie, für welches uns zurzeit keine effizienten algorithmischen Methoden zur Verfügung stehen. Dies gilt sowohl für praktische Anwendungen, als auch im Sinne der Komplexitätstheorie: Abgesehen von geringfügigen Verbesserungen, bleibt die beste obere Schranke von der Form n^O(log n) (resultierend aus der Auflistung von Erzeugendensystemen der Mächtigkeit log n), wobei n die Gruppenordnung bezeichnet.

In der vorliegenden Arbeit entwickeln wir neue algorithmische Ansätze für das Gruppenisomorphieproblem. Wir definieren und analysieren eine Reihe von kombinatorischen Algorithmen im Kontext von endlichen Gruppen, beziehungsweise allgemeiner beliebigen relationalen Strukturen. Genauer studieren wir den k-dimensionalen Weisfeiler-Leman-Algorithmus (k-WL) für natürliche Zahlen k, welcher ein essenzielles Werkzeug für das Graphenisomorphieproblem darstellt. Er ist eine wichtige Subroutine in allen kompetitiven Graphenisomorphie-Solvern und er formt einen wichtigen Baustein in Babais Quasipolynomialzeit-Algorithmus (n^O((log n)^c)) für das Graphenisomorphieproblem. Es handelt sich dabei um einen kombinatorischen Algorithmus der Laufzeit n^O(k), welcher Graphen kanonische Färbungen zuweist. Dadurch fungiert der Algorithmus als Nicht-Isomorphie-Test, mit wichtigen Verbindungen zur Logik, Spieltheorie und Graphenstrukturtheorie.

Unser erster Beitrag besteht in der Verallgemeinerung des WL-Algorithmus auf relationale Strukturen in der Form von drei möglicherweise verschiedenen Versionen. Wir vergleichen diese Versionen und zeigen, dass sie bezüglich ihrer Fähigkeit relationale Strukturen zu unterscheiden in einer Hierarchie angeordnet werden können. Das Hauptresultat ist hier, dass jede Version unter einem bestimmten Gesichtspunkt natürlich ist (und durch eine entsprechende Logik charakterisiert werden kann), aber asymptotisch alle Versionen eine vergleichbare Aussagekraft besitzen.

Insbesondere erhalten wir so eine asymptotisch robuste Definition der Weisfeiler-Leman-Dimension für relationale Strukturen, welche die kleinste natürliche Zahl k bezeichnet, sodass der k-dimensionale WL-Algorithmus eine gegebene Struktur bis auf Isomorphie identifiziert. Dies ermöglicht es uns, im Folgenden eine deskriptive Komplexitätstheorie für endliche Gruppen zu initiieren, wobei die Weisfeiler-Leman-Dimension als natürliches Komplexitätsmaß fungiert.

Wir erstellen im Laufe dieser Arbeit ein Kompendium an gruppentheoretischen Struktureigenschaften, welche von einem niedrigdimensionalen WL-Algorithmus identifiziert werden. Dies beinhaltet verschiedene wichtige Bausteine der Gruppentheorie, zum Beispiel zeigen wir, dass Gruppen, welche nicht von 5-WL unterschieden werden, stets dieselbe Multimenge an Kompositionsfaktoren besitzen. Außerdem stellen wir ein Framework bereit, welches es leicht ermöglicht, unsere Resultate zu erweitern oder an spezielle gruppentheoretische Kontexte anzupassen. Wir etablieren so weitreichende Verbindungen zwischen der WL-Dimension und der Struktur einer endlichen Gruppe und wir liefern effektive Werkzeuge für die Analyse des WL-Algorithmus auf Gruppen und verwandten algebraischen Strukturen.

Wir verwenden diese Werkzeuge dann, um obere Schranken an die WL-Dimension verschiedener wichtiger Klassen von Gruppen herzuleiten. Unter anderem zeigen wir, dass die WL-Dimension von teilerfremden Erweiterungen abelscher Gruppen oder von halbeinfachen Gruppen durch O(log log n) beschränkt ist. Des Weiteren identifizieren wir einige natürliche Klassen von Gruppen mit beschränkter WL-Dimension.

Schließlich diskutieren wir untere Schranken auf zwei Arten: Erstens geben wir explizit Gruppen an, welche für niedrigdimensionale Versionen von WL nicht unterscheidbar sind und zweitens entwerfen wir kombinatorische Reduktionen, welche die WL-Dimension asymptotisch erhalten. Letzteres liefert potenzielle Quellen für Gruppen von unbeschränkter WL-dimension.