Suppose I have a nice (e.g., word-hyperbolic? bi-automatic? automatic?) group and I want to know how big the smallest generating set is. Is that tractable (or, to put it more optimistically, what is the biggest class of groups for which it is tractable)? I am actually most interested in the question of whether there is a generating set of cardinality $2,$ but I suspect that is as hard as the general question.
EDIT What I really want to know is the answer for lattices (e.g., $SL(n, \mathbb{Z}),$) but that's probably not in any tractable class.
UPDATE It is, in fact, known that $SL(n, \mathbb{Z})$ itself is generated by $2$ elements (Hua+Reiner wrote down a generating set with three elements in 1949, as did M. Conder et al in 1992, for $SL(3, \mathbb{Z})$, but Stanton M. Trott did it with two generators in 1962). The generators are:
$\begin{pmatrix}
1 & 0 & 0 & \dots & 0 \\
1 & 1 & 0 & \dots & 0 \\
0 & 0 & 1 & \dots & 0 \\
. & . & . & \dots & .\\
0 & 0 & 0 & \dots & 1
\end{pmatrix}$
and
$\begin{pmatrix}
0 & 1 & 0 & \dots & 0\\
0 & 0 & 1 & \dots & 0\\
. & . & . & \dots & .\\
0 & 0 & 0 & \dots & 1\\
(-1)^n & 0 & 0 & \dots & 0
\end{pmatrix}$
Best Answer
I remember looking at this type of questions for finite groups and from complexity point of view. I recall it is believed (but still open) that $d(G)=2$ is a NP-complete problem even for a permutation group (given a generating set it is easy to verify that it generates the whole group, so the problem is in NP). I am not sure if this conjecture is formally stated anywhere (see here for an informal statement).
On the other hand, let me explain why it is obvious that the $d(G)=?\ 2$ problem is difficult. This has already been understood by Hall in this classical paper. Take for example $G=H^m$ where $H=A_n$ and $n!/8< m < n!/4.$ For $m=n!/8$ and $n$ large enough, $d(G)=2$, while for $m=n!/4$, $d(G)=3$. Computing where exactly the transition happens involves computing Möbius inversion of the whole subgroup lattice of $H$. This is, clearly, a Herculean task in practice if not in theory. Let me note that the probability that O(1) random elements generate $G$ goes to zero. Same story for $H=SL(2,p)$. See more here.