Złożoność obliczania kolejności grupy permutacji

Biorąc pod uwagę dwie permutacje i nad elementami (tj. ), jaka jest złożoność obliczania kolejności podgrupy generowanej przez ? Albo po prostu decydując, czy podgrupa jest rzędu(tj. wszystkie )?h n S n g , h n ! S $g$$h$$n$$S_n$$g,h$$n!$$S_n$

Jako uzupełnienie odpowiedzi Joshuy Grochow:

Obliczanie kolejności grupy permutacji dla danych generatorów odbywa się w P według algorytmu Schreiera – Simsa , patrz także str. 8-9 notatek z wykładów autorstwa Luksa. Podobnie jak przynależność do grup permutacyjnych, wielu naukowców uważało, że problem jest P-zupełny, ale ostatecznie Babai, Luks i Seress wykazali, że jest to problem NC .

Złożoność problemów dla grup permutacyjnych została dokładnie zbadana, a ich złożoność została stopniowo ustalona dla grup abelowych, grup nilpotentnych, grup rozwiązalnych, grup z ograniczonymi czynnikami składu nieabelowego, a na koniec grup (patrz praca Babai, Cook, Furst, Hopcroft, Luks, McKenzie, Mulmuley, Seress i wiele innych).

$\mathsf{NC}$

$S_n$$S_n$