Generating set-based black-box group algorithm for fixed-class nilpotency testing
|Problem being solved||fixed-class nilpotency testing problem: determine whether a group is nilpotent of a given nilpotency class, i.e., if the nilpotency class is at most the specified value.|
|Input format||a finite group given via an encoding of a group. A positive integer .|
|Output format|| Yes/No depending on whether has nilpotency class at most .|
In the case of a No answer, can also output a tuple of length whose iterated left-normed commutator is not the identity element.
|Running time|| ( times the time for group operations) + (time taken for enumeration).|
Note that almost all the time is taken coming up for the generating set. If the generating set is already available, the actual time to run the algorithm is which is .
|Competing algorithms|| brute-force black-box group algorithm for fixed-class nilpotency testing: This is much slower, but easier to code.|
randomized black-box group algorithm for fixed-class nilpotency testing
|Parallelizable version||The computations of iterated commutators can be massively parallelized, if all the parallel processes can simultaneously access the algorithms for the group operations.|
Idea and outline
We do this in two steps: