Given a finite permutation group, i.e. a subgroup of the symmetric group on $n$ symbols in terms of generators, what is the complexity of the word problem? That is, computing if two words in the generators represent the same group element?



Time Complexity of the Word Problem for Finite Permutation Groups
As has been pointed out in comments, you cannot hope to do better in general than $O(n(l\_1+l\_2))$, where $n$ is the degree of the permutation groups and $l\_1$, $l\_2$ are the lengths of the words.


But from a practical point of view it is important to observe that once a base for $G$ has been computed (see my answer to [this question](https://mathoverflow.net/questions/294351)), the word problem can be solved in time $O(k(l\_1+l\_2)$, where $k$ is the length of the base, because elements of the group are uniquely determined by their actions on the base. This is perhaps the single most important reason why bases play such a fundamental role in computations in permutation groups.


Many groups with which we wish to compute have bases of length much less than $n$, and there are lots of results (by Babai, Shalev, Liebeck, et al) proving the existence of bases with bounded length in certain families of groups. For example primitive groups other than $A\_n$ and $S\_n$ have bases of length $O(\sqrt{n} \log n)$, which can be improved to $O(\log n)$ by excluding some known families of examples.


