Low-complexity computations for nilpotent subgroup problems
Abstract
We solve the following algorithmic problems using 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.
Communicated by V. Diekert
Remember to check out the Most Cited Articles! |
---|
Check out Algebra & Computation books in the Mathematics 2021 catalogue. |