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 n
10
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 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).
źródło