Schreier–Sims algorithm

<p>The Schreier–Sims algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> in <a href="/facts/Computational_group_theory/Q9B5hL65">computational group theory</a>, named after the mathematicians <a href="/facts/Otto_Schreier/rbq7ng4v">Otto Schreier</a> and <a href="/facts/Charles_Sims_(mathematician)/14FcNkhq">Charles Sims</a>.  This algorithm can find the <a href="/facts/Order_(group_theory)/Cl3tKGFg">order</a> of a finite permutation group,  determine whether a given permutation is a member of the group, and other tasks in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>.  It was introduced by Sims in 1970, based on <a href="/facts/Schreier%27s_subgroup_lemma/bm1yyle3">Schreier's subgroup lemma</a>.  The <a href="/facts/Running_time/77T62gmf">running time</a> was subsequently improved by <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> in 1991.  Later, an even faster <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized</a> version of the algorithm was developed.
</p>

Schreier–Sims algorithm open-in-new

Schreier–Sims algorithm