How do I find the minimum size of a generating set of a group?

For example, obviously all the integer points in a $\mathbb{R}^n$ space have a minimum generating set with a size of $n$, that is, $\{(1,0,...,0),(0,1,...,0),...,(0,0,...,1)\}$.

I came across this because I was thinking what should be the generating set of the Symmetric Group $S_4$, and I thought $\{(12),(23),(34)\}$ would be reasonable, and it was shocking when I realized a smaller set $\{(12),(1234)\}$ can do the job. So is there any way I can find the minimum size of a generating set of a group? Or can I easily tell if my former guessing is wrong?

Solution 1:

Perhaps this is not quite what you want, but I can provide a computational answer to this question.

Computing the size of the minimum generating set of a finite group can be performed by an algorithm that uses at most $O(\log^2 n)$ space if the group is given as its multiplication table (as opposed to, say, a finite presentation). A brief description of the algorithm is given in Proposition 3 of The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem, by Arvind and Toran, 2006. It essentially enumerates all subsets of the group of size $\log k$ and determines if all elements of the group are reachable on the Cayley graph induced by edges labelled by elements of S.

Algorithms which use $O(\log^2 n)$ space are not quite polynomial time algorithms, but there may yet be a polynomial time algorithm out there for this computational problem.