The conjugacy problem in free solvable groups and wreath products of abelian groups is in TC^0

DOI10.1007/978-3-319-58747-9_20MaRDI QIDQ2399376zbMATH OpenOpenAlexFDO

Authors Svetla Vassileva, Armin Weiß, Alexei Myasnikov

Publication date 22 August 2017

Full work available at URL https://arxiv.org/abs/1612.05954

zbMATH Keywords

\({\mathsf {TC}^0}\)conjugacy problemfree solvable groupword problemwreath products

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Extensions, wreath products, and other compositions of groups (20E22) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16) Analysis of algorithms and problem complexity (68Q25)

Abstract: We show that the conjugacy problem in a wreath product $AwrB$ is uniform-$mathsf{TC}^0$-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 for $B$ can be replaced by the slightly weaker cyclic submonoid membership problem for $B$. Moreover, if $A$ is abelian, the cyclic subgroup membership problem suffices, which itself is uniform-$mathsf{AC}^0$-many-one-reducible to the conjugacy problem in $AwrB$. Furthermore, under certain natural conditions, we give a uniform $mathsf{TC}^0$ Turing reduction from the power problem in $AwrB$ to the power problems of $A$ and $B$. Together with our first result, this yields a uniform $mathsf{TC}^0$ solution to the conjugacy problem in iterated wreath products of abelian groups - and, by the Magnus embedding, also in free solvable groups.

Recommendations

• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• Polynomial time conjugacy in wreath products and free solvable groups.
• The geometry of the conjugacy problem in wreath products and free solvable groups.
• scientific article; zbMATH DE number 18644
• THE CONJUGACY PROBLEM IS SOLVABLE IN FREE-BY-CYCLIC GROUPS

Cites work

• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Authentication from matrix conjugation
• Characterizing \(\text{TC}^{0}\) in terms of infinite groups
• Combinatorial group theory and public key cryptography
• scientific article; zbMATH DE number 18644 (Why is no real title available?)
• scientific article; zbMATH DE number 1303030 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1754588 (Why is no real title available?)
• scientific article; zbMATH DE number 1759777 (Why is no real title available?)
• scientific article; zbMATH DE number 3394414 (Why is no real title available?)
• Log-space conjugacy problem in the Grigorchuk group
• Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)
• New constructions of public-key encryption schemes from conjugacy search problems
• On a theorem of Marshall Hall
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• On uniformity within \(NC^ 1\)
• Polynomial time conjugacy in wreath products and free solvable groups.
• Some properties of a Magnus embedding
• The Conjugacy Problem in Wreath Products and Free Metabelian Groups
• The word and geodesic problems in free solvable groups.
• Threshold circuits of small majority-depth
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(5)

• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• The geometry of the conjugacy problem in wreath products and free solvable groups.
• Polynomial time conjugacy in wreath products and free solvable groups.
• Knapsack problems for wreath products
• Log-space complexity of the conjugacy problem in wreath products

This page was built for publication: The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399376)