TY - GEN
T1 - The conjugacy problem in free solvable groups and wreath products of Abelian groups is in TC0
AU - Miasnikov, Alexei
AU - Vassileva, Svetla
AU - Weiß, Armin
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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. Moreover, if B is torsion free, the power problem for B can be replaced by the slightly weaker cyclic submonoid membership problem for B, which itself turns out to be uniform-TC0-Turing-reducible to the conjugacy problem in A B if A is non-abelian. 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 for free solvable groups.
AB - 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. Moreover, if B is torsion free, the power problem for B can be replaced by the slightly weaker cyclic submonoid membership problem for B, which itself turns out to be uniform-TC0-Turing-reducible to the conjugacy problem in A B if A is non-abelian. 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 for free solvable groups.
KW - Conjugacy problem
KW - Free solvable group
KW - TC0
KW - Word problem
KW - Wreath products
UR - http://www.scopus.com/inward/record.url?scp=85019229238&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85019229238&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-58747-9_20
DO - 10.1007/978-3-319-58747-9_20
M3 - Conference contribution
AN - SCOPUS:85019229238
SN - 9783319587462
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 217
EP - 231
BT - Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
A2 - Weil, Pascal
T2 - 12th International Computer Science Symposium in Russia, CSR 2017
Y2 - 8 June 2017 through 12 June 2017
ER -