Complejidad de calcular el orden de un grupo de permutación

Dadas dos permutaciones y sobre elementos (es decir, miembros de ), ¿cuál es la complejidad de calcular el orden del subgrupo generado por ? ¡O simplemente de decidir si el subgrupo es de orden(es decir, todo )?$g$$h$$n$$S_n$$g,h$$n!$$S_n$

Como complemento a la respuesta de Joshua Grochow:

Calcular el orden de un grupo de permutación dado generadores está en P por el algoritmo de Schreier-Sims , ver también p. 8-9 de estas notas de conferencias de Luks. Al igual que la membresía en grupos de permutación, muchos investigadores creían que el problema era P-completo, pero Babai, Luks & Seress finalmente lo demostraron en Carolina del Norte .

La complejidad de los problemas para los grupos de permutación se estudió ampliamente y su complejidad se resolvió gradualmente para grupos abelianos, grupos nilpotentes, grupos solucionables, grupos con factores de composición no abelianos limitados y finalmente grupos (ver trabajo de Babai, Cook, Furst, Hopcroft, Luks, McKenzie, Mulmuley, Seress y muchos más).

El orden de los grupos de permutación se puede calcular en tiempo polinómico. De hecho, creo incluso en y también en el tiempo casi lineal de Las Vegas. Ver, por ejemplo, el libro de Seress .$\mathsf{NC}$

Como referencia, los subgrupos de (y los algoritmos relacionados con ellos) se denominan típicamente "grupos de permutación" en lugar de simplemente "subgrupos (de )". Para que pueda googlear "algoritmos de grupo de permutación", etc.$S_n$$S_n$