The conjugacy problem in free solvable groups and wreath products of Abelian groups is in TC0

Alexei Miasnikov, Svetla Vassileva, Armin Weiß

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

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. 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.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
EditorsPascal Weil
Pages217-231
Number of pages15
DOIs
StatePublished - 2017
Event12th International Computer Science Symposium in Russia, CSR 2017 - Kazan, Russian Federation
Duration: 8 Jun 201712 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10304 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Computer Science Symposium in Russia, CSR 2017
Country/TerritoryRussian Federation
CityKazan
Period8/06/1712/06/17

Keywords

  • Conjugacy problem
  • Free solvable group
  • TC0
  • Word problem
  • Wreath products

Fingerprint

Dive into the research topics of 'The conjugacy problem in free solvable groups and wreath products of Abelian groups is in TC0'. Together they form a unique fingerprint.

Cite this