Log-space conjugacy problem in the Grigorchuk group

DOI10.1515/GCC-2017-0005zbMath1382.20038OpenAlexW2605695276MaRDI QIDQ524647

Svetla Vassileva, Alexei G. Myasnikov

Publication date: 3 May 2017

Published in: Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc-2017-0005

zbMATH Keywords

conjugacy problemGrigorchuk grouplogspace

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Groups acting on trees (20E08)

Related Items (1)

The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On groups that have normal forms computable in logspace.
• The conjugacy problem in the Grigorchuk group is polynomial time decidable.
• The complexity of Grigorchuk groups with application to cryptography
• Conjugacy problem in a class of \(2\)-groups
• Conjugacy problem in an automorphism group of an infinite tree
• Logspace Computations in Coxeter Groups and Graph Groups
• Word Problems Solvable in Logspace
• Computational Complexity

This page was built for publication: Log-space conjugacy problem in the Grigorchuk group