Schreier–Sims algorithm: Difference between revisions

Revision as of 16:00, 3 March 2024

Latest revision as of 19:53, 19 June 2024

(2 intermediate revisions by 2 users not shown)

Line 1:

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

{{inline|date=June 2024}}

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, testdetermine membership (iswhether a given permutation contained inis a member of the group?), and other tasks in [[polynomial time]]. It was introduced by Sims in 1970, based on [[Schreier's subgroup lemma]]. The [[running time]] was subsequently improved by [[Donald Knuth]] in 1991. Later, an even faster [[Randomized algorithm|randomized]] version of the algorithm was developed.

== Background and timing ==