Schreier–Sims algorithm: Difference between revisions

Revision as of 12:41, 2 October 2023

Revision as of 14:10, 3 October 2023

Line 1:

{{Short description|Algorithm for solving various problemproblems in computational group theory}}

The '''Schreier–Sims algorithm''' is an [[algorithm]] in [[computational group theory]], named after the mathematicians [[Otto Schreier]] and [[Charles Sims (mathematician)|Charles Sims]]. This algorithm can find the [[Order (group theory)|order]] of a finite permutation group, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time. It was introduced by Sims in 1970, based on [[Schreier's subgroup lemma]]. The timing was subsequently improved by [[Donald Knuth]] in 1991. Later, an even faster [[Randomized algorithm|randomized]] version of the algorithm was developed.