Brute-force black-box group algorithm for fixed-class nilpotency testing

Summary

Item	Value
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 $G$ given via an encoding of a group. A positive integer $c$.
Output format	Yes/No depending on whether $G$ has nilpotency class at most $c$. In the case of a No answer, can also output a tuple of length $c + 1$ whose iterated left-normed commutator is not the identity element.
Running time	($O(N^{c+1}c)$ times the time for group operations), plus the time taken for enumerating all group elements
Competing algorithms	generating set-based black-box group algorithm for fixed-class nilpotency testing: This is much faster, about $O(N \operatorname{polylog} N)$. However, it is harder 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

The idea is simple: take every tuple of $c + 1$ elements of $G$ (possibly repeated), and compute their iterated left-normed commutator. If this is the identity for every tuple, then that means that the nilpotency class is at most $c$.