Kemajuan terbaru dalam algoritma grup permutasi?

Saya tertarik pada algoritma untuk grup hingga seperti yang diterapkan dalam paket GAP. Tampaknya semua algoritma yang dikenal dalam bidang ini berurusan dengan kelompok permutasi / kelompok matriks; dua yang mendasar adalah Schreier-Sims [1970] dan Butler [1979], lihat misalnya 'Algoritma untuk kelompok Permutasi' oleh Alice Niemeyer sebagai referensi yang memungkinkan (?)

Oleh karena itu, saya bertanya-tanya apakah ada kemajuan signifikan di bidang ini dalam 50 tahun terakhir. Saya telah melihat bahwa pengguna NisaiVloot mengajukan beberapa pertanyaan tentang kelompok jalinan yang mungkin merupakan perpanjangan yang menarik dari hasil yang diketahui tentang kelompok permutasi, meskipun tidak jelas bagi saya bagaimana keadaan penelitian saat ini di bidang ini karena komunitas matematika / algoritme tampaknya agak keluar -sinkronisasi-saat ini.

permutations gr.group-theory Charles Mosley
sumber

Sebuah permulaan yang baik mungkin adalah melihat apakah ada anggota teori kelompok komputasi di cmsc.uwa.edu.au/research/cgt (Cheryl Praeger, Alice Niemeyer atau Serkos Seress) telah menerbitkan survei atau memberikan ceramah tentang hal itu baru-baru ini.

Anthony Labarre

Jawaban:

Tentunya ada banyak kemajuan! (Dan jika Anda benar-benar ingin bertanya tentang 50 tahun terakhir, maka itu termasuk algoritma Schreier-Sims dan Butler yang telah Anda sebutkan ...)

$\mathsf{NC}$ $n$ $O(2^{n} |G|)$ $n! \cdot poly(n)$

[1] Seress, Ákos, Algoritma grup permutasi . Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003

[2] Babai, László; Kantor, William M .; Pálfy, Péter P .; Seress, Ákos Pengenalan kotak-hitam dari grup sederhana tipe Lie yang terbatas oleh statistik pesanan elemen . J. Group Theory 5 (2002), no. 4, 383–401.

[3] László Babai, Paolo Codenotti, Youming Qiao: Tes Isomorfisme Polinomial-Waktu untuk Grup tanpa Subkelompok Normal Abelian (Extended Abstract) . Dalam: Proc. Internat ke-39. Colloq. tentang Automata, Bahasa dan Pemrograman (ICALP'12), Springer LNCS 7391, 2012, hlm. 51-62.

Joshua Grochow
sumber