The conjugacy problem in the Grigorchuk group is polynomial time decidable.

DOI10.4171/GGD/108zbMath1250.20026arXiv0808.2502OpenAlexW2002030053MaRDI QIDQ531917

Alexander Ushakov, Alexei G. Myasnikov, Igor G. Lysenok

Publication date: 21 April 2011

Published in: Groups, Geometry, and Dynamics (Search for Journal in Brave)

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

zbMATH Keywords

conjugacy problemGrigorchuk grouppolynomial time complexityconjugacy treesdecision algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Groups acting on trees (20E08)

Related Items (7)

Key agreement based on automaton groups ⋮ The conjugacy problem in automaton groups is not solvable. ⋮ Some topics in the dynamics of group actions on rooted trees. ⋮ Log-space conjugacy problem in the Grigorchuk group ⋮ Solving the Conjugacy Decision Problem via Machine Learning ⋮ Linear time algorithm for the conjugacy problem in the first Grigorchuk group ⋮ Quadratic equations in the Grigorchuk group.

Uses Software

• CRAG

Cites Work

• On Burnside's problem on periodic groups
• 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
• Conjugacy separability of certain torsion groups
• On a problem of Day on nonelementary amenable groups in the class of finitely presented groups
• Subgroups of finitely presented groups
• Random subgroups and analysis of the length-based and quotient attacks
• CONSTRUCTIVE ALGEBRAS I
• Cryptography and Coding
• Computable Algebra, General Theory and Theory of Computable Fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The conjugacy problem in the Grigorchuk group is polynomial time decidable.