Small generating set-finding problem for black-box groups

From Groupprops
Jump to: navigation, search

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_2N.

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^2N) 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_2N + 1}\log_2N) 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^2N) where N is the order of the group. generating set-based black-box group algorithm for abelianness testing takes time O(N\log_2^2N) 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.