Low-complexity computations for nilpotent subgroup problems

2017/06/04 by Macdonald, Jeremy, Miasnikov, Alexei, Ovchinnikov, Denis
#20F18 #68Q25 #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1706.01092

Abstract

We solve the following algorithmic problems using TC0 circuits, or in logspace and quasilinear time, uniformly in the class of nilpotent groups with bounded nilpotency class and rank: subgroup conjugacy, computing the normalizer and isolator of a subgroup, coset intersection, and computing the torsion subgroup. Additionally, if any input words are provided in compressed form as straight-line programs or in Mal'cev coordinates the algorithms run in quartic time.

Related

• TC⁰ circuits for algorithmic problems in nilpotent groups
• Logspace and compressed-word computations in nilpotent groups
• Non-commutative lattice problems
• Effective Twisted Conjugacy Separability of Nilpotent Groups
• Decomposability of Finitely Generated Torsion-free Nilpotent Groups