Small generating set-finding problem for black-box groups
This article describes a basic computational problem in computational group theory
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).
|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.|
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.
|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.|