We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC<sup>0</sup>.
- Authors
Miasnikov, Alexei; Vassileva, Svetla; Weiß, Armin
- Abstract
We show that the conjugacy problem in a wreath product A ≀ 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-AC0-many-one-reducible to the conjugacy problem in A ≀ B. Furthermore, under certain natural conditions, we give a uniform TC0 Turing reduction from the power problem in A ≀ 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.
- Subjects
SOLVABLE groups; GROUP products (Mathematics); FREE groups; ABELIAN groups; WREATH products (Group theory)
- Publication
Theory of Computing Systems, 2019, Vol 63, Issue 4, p809
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-018-9849-2