Let’s define presentation problem for finite groups as the following algorithmic problem:
You are given a list of permutations $g_0, …, g_k$ (written in form of products of independent cycles). Output some presentation of $\langle g_1, … , g_k \rangle$
What is the computational complexity of this problem?
If $n$ is the length of input, then the problem can be solved for $2^{O(n \log(n))}$ time worst case via breadth-first traversal of Cayley graph of $\langle g_1, … , g_k \rangle$ (which has $\leq n!$ vertices and $\leq (n+ 1)!$ edges). But maybe there is some way to do it faster?
Best Answer
I think this question needs an answer! A presentation of a subgroup of $S_n$ defined by generating permutations can be computed in polynomial time using the Schreier-Sims algorithm to compute a base and strong generating set of the group $G$. This can be used to write down a presentation.
I don't want to go into details about the algorithm - there are plenty of available descriptions, starting with the Wikipedia page. The idea is to compute a stabilizer chain $$G = G^{(1)} > G^{(2)} > \cdots G^{(b)} > G^{(b+1)} = 1$$ of $G$, and to extend the initial generating set to a strong generating set, which contains generators of each of the subgroups in the chain. This involves computing (right) transversals $U^{(i)}$ of $G^{(i+1)}$ in $G^{(i)}$.
The relations in the presentation then consist of relations to define the new generators as words in the old, together with those of form $u_{ij}g = w$, for each $u_{ij} \in U^{(i)}$ and each generator $g$ of $G^{(i)}$, where $w$ is a word in the generators of $G^{(i)}$.
There are (at least) two versions, according to whether you store the elements $u_{ij}$ of $U^{(i)}$ explicitly (in which case you would introduce $u_{ij}$ as a new generator, and $w$ would be a single generator $u_{ij'}$), or whether you use words in the strong generators to represent the $u_{ij}$. Both versions are polynomial in $k$ and $n$ (linear in $k$). The first one has better time complexity but may be prohibitive in terms of memory usage for large $n$.
A lot of research in permutation group algorithms has involved the search for nearly linear time algorithms, which means $O(nk\log^c|G|)$ for some $c$. These are most useful for small base groups (where the length $b$ of the stabilizer chain is small), and $|G| \le n^b$. The book Permutation Group Algorithms by Ákos Seress is a good reference.
As Alexander Hulpke mentioned in his now deleted answer, we almost have a nearly linear time algorithm for computing a BSGS, and the principal remaining obstruction to this is the lack of a known short presentation for the simple groups $^2G_2(q)$.
In practice, the presentation computed using this method is unwieldy and is likely to have huge numbers of redundant relations. There is a variant of Schreier-Sims, know as the Todd-Coxeter Schreier-Sims, which generally produces a much shorter presentation, and is often quicker as well.
The idea is, for each $i$ with $1 \le i \le b$ (where actually we do this in reverse order $i=b,b-1,\ldots,1$), we calculate a small number of the relations $u_{ij}g = w$, and then use coset enumeration to see if they (together with the relations for larger $i$, which have already been computed) suffice to prove that the index in the associated finitely presented group is equal to the correct index $[G^{(i)}:G^{(i+1)}]$. If so, then we have enough relations, and there is the added advantage that we can abort the calculations in the Schreier-Sims algorithm for that $i$. If the coset enumeration does not complete quickly with the correct answer, then we interrupt it and adjoin a new relation $u_{ij}g = w$ that does not appear to be a consequence of the existing ones.
This works very well in practice, but it is unfortunately difficult (and probably impossible) to estimate its complexity, because the theoretical unsolvability of the word problem implies that the complexity of coset enumeration in general (not necessarily in this specific situation) is not recursive.