Kompleksitas menghitung urutan kelompok permutasi

Diberikan dua permutasi dan atas elemen (yaitu, anggota ), apa kompleksitas menghitung urutan subkelompok yang dihasilkan oleh ? Atau hanya memutuskan apakah subkelompok itu berurutan(yaitu, semua )?$g$$h$$n$$S_n$$g,h$$n!$$S_n$

Sebagai pelengkap jawaban Joshua Grochow:

Komputasi urutan grup permutasi yang diberikan generator adalah dalam P oleh algoritma Schreier-Sims , lihat juga hal. 8-9 dari catatan kuliah ini oleh Luks. Sama seperti keanggotaan dalam kelompok permutasi, masalah itu diyakini sebagai P-lengkap oleh banyak peneliti, tetapi akhirnya ditunjukkan di NC oleh Babai, Luks & Seress .

Kompleksitas masalah untuk kelompok permutasi dipelajari secara luas dan kompleksitasnya secara bertahap diselesaikan untuk kelompok abelian, kelompok nilpoten, kelompok yang dapat dipecahkan, kelompok dengan faktor komposisi non-abelian yang terikat, dan akhirnya kelompok (lihat karya Babai, Cook, Furst, Hopcroft, Luks, McKenzie, Mulmuley, Seress dan banyak lagi).

Urutan kelompok permutasi dapat dihitung dalam waktu polinomial. Bahkan, saya percaya bahkan pada dan waktu Las Vegas yang hampir linier. Lihat, misalnya, buku karya Seress .$\mathsf{NC}$

Untuk referensi, subkelompok (dan algoritme yang terkait dengannya) biasanya disebut "grup permutasi" daripada sekadar "subkelompok (dari )". Jadi Anda dapat google "algoritma grup permutasi" dll.$S_n$$S_n$