The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0

摘要

We show that the conjugacy problem in a wreath product A (sic) B is uniform-TC0-Turing-reducible to the conjugacy problem in the factors A and B and the power problem in B. If B is torsion free, the power problem in B can be replaced by the slightly weaker cyclic submonoid membership problem in B. Moreover, if A is abelian, the cyclic subgroup membership problem suffices, which itself is uniform-AC(0)-many-one-reducible to the conjugacy problem in A (sic) B. Furthermore, under certain natural conditions, we give a uniform TC0 Turing reduction from the power problem in A (sic) B to the power problems of A and B. Together with our first result, this yields a uniform TC0 solution to the conjugacy problem in iterated wreath products of abelian groups - and, by the Magnus embedding, also in free solvable groups.