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

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

Aryeh
źródło

Odpowiedzi:

9

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

Michael Blondin
źródło
Kiedy Mulmuley pracował na algorytmach grup permutacyjnych? (Poza problemem Kroneckera, który jest prawdopodobnie czymś zupełnie innym ...)
Joshua Grochow
Być może nie powinienem był umieszczać go na liście, ale miałem na myśli ten artykuł: link.springer.com/article/10.1007%2FBF02579205, który zezwalał na wyniki w grupach permutacyjnych, w szczególności w tym artykule Cook & McKenzie: epubs.siam .org / doi / abs / 10.1137 / 0216058 .
Michael Blondin,
W porządku (wygląda na to, że nie wiedział, że pracuje nad algorytmem grupy permutacji, ale Cook-McKenzie wykazał, że jest równoważny).
Joshua Grochow
12

NC

SnSn

Joshua Grochow
źródło