Small generating set-finding problem for permutation encodings

Description

A group $G$ acting on a set $S$ of size $n$, described by means of a generating set $A$ of $G$.

Find a generating set for $G$ whose size is bounded by some fixed polynomial in $n$, in time proportional to $|A|$ times a fixed polynomial in $n$.

Particular algorithms

• Jerrum's filter outputs a Jerrum-reduced generating set, which has size at most $n-1$. The time it takes is $|A|n^{4}$. The critical step in this algorithm in the iterated step of making changes at cycles.
• Sims filter outputs a Sims-reduced generating set.

Reductions

Reduction to generating set-checking problem

The generating set-finding problem has a nondeterministic reduction to the generating set-checking problem: first guess a generating set, then check if it works.

Importance

Many problems, including the testing of group properties and subgroup properties, have algorithms that proceed much faster if a generating set of small size is available. Thus, the small generating set-finding algorithms are typically used in conjunction with the generating set-dependent algorithms.