The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0
| Autor: | Alexei Miasnikov, Armin Weiß, Svetla Vassileva |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Pure mathematics
Conjugacy problem 010102 general mathematics 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Mathematics::Group Theory Computational Theory and Mathematics 010201 computation theory & mathematics Wreath product Turing reduction Iterated function Solvable group Torsion (algebra) Embedding 0101 mathematics Abelian group Computer Science::Databases Mathematics |
| Zdroj: | Theory of Computing Systems. 63:809-832 |
| ISSN: | 1433-0490 1432-4350 |
| DOI: | 10.1007/s00224-018-9849-2 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink