The parallel complexity of certain algorithmic problems in group theory

Abstract

In this thesis, we study the parallel complexity of certain problems in algorithmic group theory. These problems are the word problem, the geodesic and normal form problem and the conjugacy problem. We study these problems for some products of groups, namely direct products, free products and graph products. For all those we consider the problems for a fixed group as well as the uniform versions. Uniform means that the group is part of the input. Among the studied problems, the word problem is the most important one and necessary to solve any of the other problems. For direct products, solving any of the mentioned problems reduces directly to the problems in the base groups of the product. Some of the solutions for the direct product are required for solving the problems of the more complicated products. For free products, we show that the word problem reduces in AC^0 to the word problem of the base groups and the word problem of the free group of rank two. This does hold for the word problem of a fixed free product as well as for the uniform version. For the geodesic and normal form problem of free products, we introduce an equivalence relation. This relation can be decided in AC^0 by using oracle calls to the word problems of the base groups. The solution of the word and geodesic problem can then be used to solve the conjugacy problem. In free products, two cyclically reduced words are conjugate if and only if they are transposed. Direct products and free products are special cases of graph products. A graph product can be written as an amalgamated product of smaller graph products. We first solve the word problem of some restricted amalgamated product. This solution can then be used to solve the word problem of a fixed graph product inductively. We obtain that the word problem of a fixed graph product is AC^0-reducible to the word problem of its base groups and the word problem of the free group of rank two. Unfortunately, this method cannot be used to solve the uniform word problem. We show that the uniform word problem of graph products is NL-hard. For solving it, we introduce an embedding of the graph product into the automorphism group of some (possibly infinite dimensional) vector space. We show that the evaluation of these automorphisms can be realized in GapL and that verifying its result is in CL by using oracle calls to the word problem in the base groups. The uniform word problem of graph products can be reduced to the evaluation of these automorphisms. For the geodesic problem, we introduce another equivalence relation. As for free products, this relation can be decided in AC^0 by using oracle calls to the (uniform) word problem. In graph products the normal form of some word is the length-lexicographic first equivalent word. For solving the normal form problem, first a geodesic and then the lexicographic normal form of this geodesic is computed. We show that for a fixed graph product the computation of the lexicographic normal form is in TC^0 and TC^0-complete for most graph products. We further show that the uniform version is FNL-complete. The solution of the word and geodesic problem can then be used to solve the conjugacy problem. First, we show how to compute cyclically reduced words in AC^0 by using oracle calls to the word problem. Then we show that in graph products two cyclically reduced words are conjugate if and only if they are obtained by a sequence of transpositions. This problem can then be solved by verifying whether the first word is a factor of some power of the second word. For a fixed graph product the factor problem can be decided in AC^0 by using oracle calls to the word problem. For the uniform factor problem we show that it can be decided in NL by using oracle calls to the uniform word problem. Combining all this gives a solution to the (uniform) conjugacy problem of graph products.

In dieser Arbeit untersuchen wir die parallele Komplexität gewisser Probleme in der algorithmischen Gruppentheorie. Diese Probleme sind das Wortproblem (engl. word problem), das Geodäten- und Normalformenproblem (engl. geodesic and normal form problem) und das Konjugationsproblem (engl. conjugacy problem). Wir untersuchen diese Probleme für Produkte von Gruppen, genauer für direkte Produkte, freie Produkte und Graphprodukte. Für all jene betrachten wir die Probleme sowohl für eine feste Gruppe als auch ihre uniforme Variante. Uniform bedeutet, dass die Gruppe Teil der Eingabe ist. Unter den untersuchten Problemen ist das Wortproblem das wichtigste und notwendig für die Lösung der anderen Probleme. Die erwähnten Probleme lassen sich für direkte Produkte unmittelbar durch reduzieren auf die Probleme in den Basisgruppen lösen. Manche der Lösungen für direkte Produkte werden benötigt, um die Probleme in den komplizierteren Produkten zu lösen. Für freie Produkte können wir zeigen, dass sich das Wortproblem in AC^0 auf das Wortproblem der Basisgruppen und das Wortproblem der freien Gruppe vom Rang zwei reduzieren lässt. Dies gilt sowohl für das Wortproblem eines festen freien Produkts als auch für die uniforme Variante. Für das Geodäten- und Normalformenproblem freier Produkte führen wir eine Äquivalenzrelation ein. Diese Relation kann in AC^0 durch Orakelanfragen an das Wortproblem des freien Produkts entschieden werden. Die Lösung des Wort- und Geodätenproblems kann schließlich genutzt werden, um das Konjugationsproblem zu lösen. In freien Produkten sind zwei zyklisch reduzierte (engl. cyclically reduced) Wörter genau dann konjugiert, wenn sie transponiert zueinander sind. Direkte Produkte und freie Produkte sind Spezialfälle des Graphprodukts. Ein Graphprodukt kann als amalgamiertes Produkt kleinerer Graphprodukte aufgefasst werden. Wir lösen zuerst das Wortproblem dieser eingeschränkten amalgamierten Produkte. Diese Lösung kann schließlich genutzt werden, um das Wortproblem eines festen Graphprodukts induktiv zu lösen. Wir erhalten, dass das Wortproblem eines festen Graphprodukts AC^0-reduzierbar auf das Wortproblem in den Basisgruppen und das Wortproblem der freien Gruppe vom Rang zwei ist. Diese Methode lässt sich nicht für das uniforme Wortproblem in Graphprodukten nutzen. Wir zeigen, dass das uniforme Wortproblem von Graphprodukten NL-schwer ist. Um dieses zu lösen führen wir eine Einbettung des Graphprodukts in die Automorphismengruppe eines (möglicherweise unendlich dimensionalen) Vektorraums ein. Wir zeigen, dass durch Orakelanfragen an das Wortproblem in den Basisgruppen, die Auswertung dieser Automorphismen in GapL realisiert werden kann und, dass die Verifikation des Ergebnisses in CL ist. Das uniforme Wortproblem kann auf die Auswertung dieser Automorphismen reduziert werden. Für das Geodätenproblem führen wir eine weitere Äquivalenzrelation ein. Wie schon für freie Produkte kann diese Relation in AC^0 durch Orakelanfragen an das (uniforme) Wortproblem entschieden werden. Die Normalform eines Wortes ist das längenlexikographisch erste äquivalente Wort. Um das Normalformenproblem zu lösen wird zuerst eine Geodätische und anschließend die lexikographische Normalform dieser Geodätischen berechnet. Wir zeigen, dass die Berechnung der lexiographischen Normalform in TC^0 möglich ist und TC^0-vollständig für die meisten Graphprodukte ist. Wir zeigen außerdem, dass die uniforme Variante FNL-vollständig ist. Die Lösung des Wort- und Geodätenproblems kann schließlich genutzt werden, um das Konjugationsproblem zu lösen. Wir zeigen zuerst, wie sich zyklisch reduzierte Wörter in AC^0 durch Orakelanfragen an das Wortproblem berechnen lassen. Anschließend zeigen wir, dass in Graphprodukten zwei zyklisch reduzierte Wörter genau dann konjugiert sind, wenn sie durch eine Folge von Transpositionen auseinander hervorgehen. Dieses Problem kann schließlich gelöst werden, indem geprüft wird, ob das erste Wort ein Faktor einer Potenz des zweiten Worts ist. Für ein festes Graphprodukt kann das Faktorproblem in AC^0 durch Orakelanfragen an das Wortproblem entschieden werden. Für das uniforme Faktorproblem zeigen wir, dass es in NL durch Orakelanfragen an das uniforme Wortproblem entschieden werden kann. Zusammengesetzt ergibt sich eine Lösung des (uniformen) Konjugationsproblems.