A polynomial algorithm to determine whether a finite group is nilpotent Does there exist a polynomial (in respect to the order of the group) algorithm that given a Cayley table of a finite group determines, whether a group is nilpotent or not?
There do exist polynomial algorithms, that determine, whether a group is nilpotent of degree k or not. The simplest of them is simply checking the necessary commutator identity for all $(k + 1)$-ples of elements of the group (this algorithm works for $O(n^{k + 1})$, where $n$ is the order of the group). However, none of them can be used to determine in polynomial time, whether a group is nilpotent of arbitrary degree. 

A simple (but inefficient) way to test nilpotency in polynomial time would be to compute its lower central series and see whether the final group is trivial or not.
Each commutator subgroup computation takes $O(n^2)$ time, and since the orders of the groups in this central series do not increase, they must stabilise in at most $O(\log n)$ steps (by way of the fundamental theorem of arithmetic – the worst case is when the orders halve at each step). Thus, this algorithm takes $O(n^2\log n)$ time.
