The parallel complexity of certain algorithmic problems in group theory
Jonathan Kausch · OPUS Publication Server of the University of Stuttgart (University of Stuttgart) · 2017
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.