Small generating set-finding problem for black-box groups

This article describes a basic computational problem in computational group theory

Description

We are given a group $G$ of order $N$ is specified by means of an encoding. We need to find a generating set for $G$ of size at most $\log _{2}N$.

A somewhat stronger requirement (which will guarantee this one) is: we need to find a generating set in which no element is redundant (that is, throwing out any element makes the subset non-generating).

Algorithms

Deterministic algorithms

Algorithm name	Time taken	Comments
Black-box group algorithm for small generating set-finding problem	Takes time $O(N\log _{2}^{2}N)$ times the time for group operations. This is polynomial time in the order of the group.	Does not necessarily find a generating set of minimum size, but (in one version) it finds a minimal generating set (i.e., a generating set in which no element is redundant). If the max-length is $\ell$, takes time $O(N\ell ^{2})$ times the time for group operations.
Black-box group algorithm for minimum size generating set-finding problem	Takes time $O(N^{\log _{2}N+1}\log _{2}N)$ times the time for group operations. This is not polynomial time but is quasipolynomial time in the order of the group.	Finds a generating set of minimum size. If the minimum size of generating set is $s$, takes time $O(N^{s+1}s)$ times the time for group operations.

Nondeterministic algorithms

The generating set-finding problem has a clear nondeterministic reduction to the generating set-checking problem -- first nondeterministically obtain a generating set, then invoke the generating set-checking problem to verify that it is genuinely a generating set.

Significance

Importance statement	What it means	Algorithm(s) we're using	Examples of this
Conversion of black-box group algorithm dependent on generating set to black-box group algorithm	For the black-box group version, we obtain that if there is a polynomial-time algorithm (polynomial in the order of the group) for carrying out a particular task given a generating set, then there is also a polynomial-time algorithm in general.	Black-box group algorithm for small generating set-finding problem, which is $O(N\log _{2}^{2}N)$ where $N$ is the order of the group.	generating set-based black-box group algorithm for abelianness testing takes time $O(N\log _{2}^{2}N)$ and is thus faster than brute-force black-box group algorithm for abelianness testing, which takes time $O(N^{2})$.
Conversion of black-box group algorithm dependent on generating set to nondeterministic black-box group algorithm	This converts to black-box group algorithm dependent on a choice of generating set to a nondeterministic black-box group algorithm.