Low-complexity computations for nilpotent subgroup problems
2019
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
2
Citations
NaN
KQI