Un algoritmo polinómico para determinar si un grupo finito es nilpotente

Question

¿Existe un algoritmo polinómico (respecto al orden del grupo) que dada una tabla de Cayley de un grupo finito determine, si un grupo es nilpotente o no?

Existen algoritmos polinómicos que determinan si un grupo es nilpotente de grado k o no. La más sencilla de ellas es simplemente comprobar la identidad de conmutador necesaria para todos los $(k + 1)$ -de elementos del grupo (este algoritmo funciona para $O(n^{k + 1})$ , donde $n$ es el orden del grupo). Sin embargo, ninguno de ellos puede utilizarse para determinar en tiempo polinómico si un grupo es nilpotente de grado arbitrario .

Answer 1

Una forma sencilla (pero ineficiente) de comprobar la nilpotencia en tiempo polinómico sería calcular su serie central inferior y ver si el grupo final es trivial o no.

Cada cálculo de subgrupo conmutador requiere $O(n^2)$ tiempo, y como los órdenes de los grupos de esta serie central no aumentan, deben estabilizarse como máximo en $O(\log n)$ pasos (por medio del teorema fundamental de la aritmética - el peor caso es cuando los órdenes se reducen a la mitad en cada paso). Así, este algoritmo tarda $O(n^2\log n)$ tiempo.