Ich interessiere mich für Algorithmen für endliche Gruppen, wie sie im GAP-Paket implementiert sind. Es scheint, dass alle bekannten Algorithmen in diesem Bereich Permutationsgruppen / Matrixgruppen behandeln; zwei grundlegende sind Schreier-Sims [1970] und Butler [1979], siehe zB 'Algorithmen für Permutationsgruppen' von Alice Niemeyer als mögliche Referenz (?)
Daher habe ich mich gefragt, ob in den letzten 50 Jahren auf diesem Gebiet erhebliche Fortschritte erzielt wurden. Ich habe gesehen, dass Benutzer NisaiVloot einige Fragen zu Geflechtgruppen gestellt hat, die eine interessante Erweiterung bekannter Ergebnisse zu Permutationsgruppen darstellen könnten, obwohl mir unklar ist, wie der aktuelle Forschungsstand auf diesem Gebiet ist, da die Mathematik- / Algorithmus-Communitys etwas uneinheitlich zu sein scheinen -von-synchron heutzutage.
quelle
Antworten:
Sicherlich hat es Unmengen von Fortschritten gegeben! (Und wenn Sie wirklich nach den letzten 50 Jahren fragen wollten , dann gehören dazu die Algorithmen von Schreier-Sims und Butler, die Sie bereits erwähnt haben ...)
[1] Seress, Ákos Permutationsgruppenalgorithmen . Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003
[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos Black-Box-Erkennung endlicher einfacher Gruppen vom Lie-Typ durch Statistik der Elementreihenfolgen . J. Group Theory 5 (2002), No. 4, 383–401.
[3] László Babai, Paolo Codenotti, Youming Qiao: Polynom-Zeit-Isomorphismus-Test für Gruppen ohne abelsche normale Untergruppen (Extended Abstract) . In: Proc. 39. Internat. Colloq. zu Automaten, Sprachen und Programmierung (ICALP'12), Springer LNCS 7391, 2012, S. 51-62.
quelle