Complexidade da computação da ordem de um grupo de permutação

Dadas duas permutações e sobre elementos (ou seja, membros de ), qual é a complexidade de calcular a ordem do subgrupo gerado por ? Ou apenas decidir se o subgrupo está na ordem(ou seja, todos os )?h n S n g , h n ! S $g$$h$$n$$S_n$$g,h$$n!$$S_n$

Como complemento à resposta de Joshua Grochow:

A computação da ordem de um grupo de permutação dado a geradores está em P pelo algoritmo de Schreier-Sims , veja também a p. 8-9 dessas notas de palestras de Luks. Assim como a participação em grupos de permutação, o problema foi considerado P-completo por muitos pesquisadores, mas finalmente foi demonstrado como sendo no NC por Babai, Luks & Seress .

A complexidade dos problemas para grupos de permutação foi extensivamente estudada e sua complexidade foi gradualmente estabelecida para grupos abelianos, grupos nilpotentes, grupos solucionáveis, grupos com fatores de composição não-abelianos limitados e finalmente grupos (ver trabalho de Babai, Cook, Furst, Hopcroft, Luks, McKenzie, Mulmuley, Seress e muitos mais).

A ordem dos grupos de permutação pode ser calculada em tempo polinomial. Na verdade, acredito que mesmo em e também no tempo quase linear de Las Vegas. Veja, por exemplo, o livro de Seress .$\mathsf{NC}$

Para referência, os subgrupos de (e algoritmos relacionados a eles) são normalmente chamados de "grupos de permutação" em vez de meramente "subgrupos (de S n )". Então você pode pesquisar no Google "algoritmos de grupo de permutação" etc.$S_n$$S_n$