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

10

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 nghnSng,hn!Sn

Aryeh
fonte

Respostas:

9

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).

Michael Blondin
fonte
Quando Mulmuley trabalhou nos algoritmos de grupos de permutação? (Para além do problema Kronecker, que é sem dúvida um tipo muito diferente de coisa ...)
Joshua Grochow
Talvez eu não devesse incluí-lo na lista, mas estava me referindo a este artigo: link.springer.com/article/10.1007%2FBF02579205 que permitiu resultados em grupos de permutação, em particular neste artigo de Cook & McKenzie: epubs.siam .org / doi / abs / 10.1137 / 0216058 .
Michael Blondin
É justo (parece que ele não sabia que estava trabalhando no algoritmo do grupo de permutação, mas Cook-McKenzie mostrou que era equivalente).
Joshua Grochow
12

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 .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.SnSn

Joshua Grochow
fonte