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?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ The obvious algorithm that just computes both permutations explicitly takes $O(n(l_1+l_2))$ time where $l_1$ and $l_2$ are the lengths of the two words. I'd guess that's close to optimal unless you make special assumptions about the generators. $\endgroup$– Johannes HahnMar 6, 2018 at 18:20
-
1$\begingroup$ In terms of structural complexity, the problem can be computed in the class DET, as one can reduce it to multiplication of the corresponding sequence of permutation matrices. $\endgroup$– Emil JeřábekMar 6, 2018 at 18:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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), 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.
answered Mar 7, 2018 at 8:56