Étant donné deux permutations et h sur n éléments (c'est-à-dire les membres de S n ), quelle est la complexité du calcul de l'ordre du sous-groupe généré par g , h ? Ou tout simplement de décider si le sous-groupe est d'ordre n ! (c'est-à-dire, tout S n )?
En complément de la réponse de Joshua Grochow:
Le calcul de l'ordre d'un groupe de permutation donné aux générateurs est en P par l' algorithme de Schreier-Sims , voir aussi p. 8-9 de ces notes de cours de Luks. Tout comme l'appartenance à des groupes de permutation, le problème était considéré comme P-complet par de nombreux chercheurs, mais il a finalement été démontré qu'il était en NC par Babai, Luks & Seress .
La complexité des problèmes pour les groupes de permutation a été largement étudiée et leur complexité a été progressivement réglée pour les groupes abéliens, les groupes nilpotents, les groupes résolubles, les groupes avec des facteurs de composition non abéliens bornés et enfin les groupes (voir les travaux de Babai, Cook, Furst, Hopcroft, Luks, McKenzie, Mulmuley, Seress et bien d'autres).
la source