Let $G \leq {\rm S}\_n$ be a finite permutation group, and let
$S = \{g\_1, \dots, g\_k\}$ be a generating set for $G$ which is closed
under inversion and which does not contain the identity.
The *growth function* of $G$ with respect to $S$ is the sequence
$(a\_0, a\_1, a\_2, \dots)$, where $a\_r$ is the number of elements of $G$
which can be written as products of $r$, but no fewer, generators $g\_i$.
The *diameter* of $G$ with respect to $S$ is the largest $r$ such that
$a\_r > 0$.



> 
> **Question:** How hard is it to compute the diameter and the
>  growth function of a given permutation group $G$ of degree $n$?
>  Or more specifically: using current computer technology, is it feasible
>  to do this for any given group $G$ of degree $n \leq 100$ and any given
>  sufficiently small generating set $S$?
> 
> 
> 


The motivation for this question is that while the [Schreier-Sims algorithm](http://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm)
allows e.g. to compute the order of such groups and to perform element tests 
instantaneously, even only computing the diameter of the Rubik's Cube Group
with respect to its natural generating set was a [major effort](http://www.cube20.org/) --
and its growth function is apparently not known in full so far.


My feeling goes in the direction that one can do essentially better,
i.e. that it should be possible to find an algorithm for computing
diameter and growth function which is by orders of magnitude more
efficient than enumerating group elements by brute force.
However maybe I am wrong, and somebody can point out reasons why
these problems cannot be solved efficiently?



How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?
I just came across this question and, even though I'm a bit late, I thought you might be interested in this reference: 


*Even, S.; Goldreich, O.*, [**The minimum-length generator sequence problem is NP-hard**](http://dx.doi.org/10.1016/0196-6774(81)90029-8), J. Algorithms 2, 311-313 (1981). [ZBL0467.68046](https://zbmath.org/?q=an:0467.68046).


This asserts that the calculation of the diameter of a Cayley graph of a permutation group is NP-Hard. I don't have access to the article myself but, from what I've read elsewhere, I believe this statement remains true even if you restrict to elementary-abelian 2-groups. (Which seems astonishing to me!)


