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

DOI10.4171/GGD/108MaRDI QIDQ531917zbMATH OpenOpenAlexFDO

Authors Alexander Ushakov, Igor Lysenok, Alexei Myasnikov

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 problemconjugacy treesdecision algorithmsGrigorchuk grouppolynomial time complexity

Mathematics Subject Classification ID

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

Abstract: In this paper we prove that the Conjugacy Problem in the Grigorchuk group $Gamma$ has polynomial time complexity.

Recommendations

• Computational complexity and the conjugacy problem
• Time complexity of the conjugacy problem in relatively hyperbolic groups.
• Polynomial time conjugacy in wreath products and free solvable groups.
• Conjugacy problem in a class of \(2\)-groups
• Generic-case complexity, decision problems in group theory, and random walks.

Cites work

• Computable Algebra, General Theory and Theory of Computable Fields
• Conjugacy problem in a class of \(2\)-groups
• Conjugacy problem in an automorphism group of an infinite tree
• Conjugacy separability of certain torsion groups
• CONSTRUCTIVE ALGEBRAS I
• Cryptography and Coding
• scientific article; zbMATH DE number 66487 (Why is no real title available?)
• scientific article; zbMATH DE number 1267534 (Why is no real title available?)
• scientific article; zbMATH DE number 1284170 (Why is no real title available?)
• scientific article; zbMATH DE number 1544074 (Why is no real title available?)
• scientific article; zbMATH DE number 2156384 (Why is no real title available?)
• On a problem of Day on nonelementary amenable groups in the class of finitely presented groups
• On Burnside's problem on periodic groups
• Random subgroups and analysis of the length-based and quotient attacks
• Solved and unsolved problems around one group.
• Subgroups of finitely presented groups
• The complexity of Grigorchuk groups with application to cryptography

Cited in

(8)

• The conjugacy problem in automaton groups is not solvable.
• Key agreement based on automaton groups
• Quadratic equations in the Grigorchuk group.
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Solving the conjugacy decision problem via machine learning
• Linear time algorithm for the conjugacy problem in the first Grigorchuk group
• Log-space conjugacy problem in the Grigorchuk group
• Some topics in the dynamics of group actions on rooted trees.

Describes a project that uses

Uses Software

• CRAG

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

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