Polynomial time conjugacy in wreath products and free solvable groups

DOI10.1515/gcc.2011.005zbMath1242.20038arXiv1011.5931MaRDI QIDQ2882827

Svetla Vassileva

Publication date: 7 May 2012

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

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

zbMATH Keywords

complexity; wreath products; conjugacy problem; free solvable groups; conjugacy search problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

20F16: Solvable groups, supersolvable groups

20E22: Extensions, wreath products, and other compositions of groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Related Items

THE MAGNUS EMBEDDING IS A QUASI-ISOMETRY, Unnamed Item, Logspace and compressed-word computations in nilpotent groups, Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}, Algorithmic theory of free solvable groups: randomized computations., The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\), The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\), Spherical quadratic equations in free metabelian groups, A family of polycyclic groups over which the uniform conjugacy problem is NP-complete, Time complexity of the conjugacy problem in relatively hyperbolic groups

Cites Work

• Small cancellation theory and automatic groups. II
• Conjugacy in polycyclic groups
• SOLVING THE WORD PROBLEM IN REAL TIME
• An example of a finitely presented amenable group not belonging to the classEG
• Conjugacy in Nilpotent Groups
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS