Small generating set-finding problem for black-box groups
From Groupprops
This article describes a basic computational problem in computational group theory
Contents
Description
We are given a group of order is specified by means of an encoding. We need to find a generating set for of size at most .
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 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 , takes time times the time for group operations. |
Black-box group algorithm for minimum size generating set-finding problem | Takes time 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 , takes time 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 where is the order of the group. | generating set-based black-box group algorithm for abelianness testing takes time and is thus faster than brute-force black-box group algorithm for abelianness testing, which takes time . |
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. |