Given a finite permutation group $G$ (a subgroup of the symmetric group on a finite set) in terms of its generators, what is known about the decision problem of deciding if $G$ is $k$-transitive for a given $k \ge 1$?


What can we say about the complexity of this problem, and in what complexity class is it contained?



Complexity of decision problem to decide if permutation group is $k$-transitive
There have been several articles on this forum discussing these topics, but here is a quick review.


A *base* $B$ for a subgroup $G \le {\rm Sym}(X)$ is a sequence $(\alpha\_1,\ldots,\alpha\_k)$ of points in $X$, such that the stabilizer $G\_B$ of the sequence (i.e. the intersections of the stabilizers of the $\alpha\_i$) is trivial.


For $1 \le i \le k+1$, let $G^{(i)}$ denote the stabilizer of the initial subsequence $(\alpha\_1,\ldots,\alpha\_{i-1})$ of $B$ (so $G^{(1)}=G$ and $G^{(k+1)} = G\_B = 1$).


An *strong generating set* of $G$ w.r.t $B$ is a generating set that includes generators of each of the subgroup $G^{(i)}$.


Given a strong generating set, we can easily calculate the *basic orbits*, which are the orbits of $\alpha\_i$ under $G\_i$ for $1 \le i \le k$, and the order of $G$ is the product of the lengths of the basic orbits. In particular, $G$ is $k$-transitive if and only if the sequence of basic orbit lengths starts $n,n-1,\ldots,n-k+1$ where $n=|X|$.


The Schreier-Sims algorithm computes a base and strong generating set for $G$ in polynomial time, given an arbitrary generating set as input. There are many heuristics and tricks that can be used to speed it up in certain situations, and some of these were used by Sims (who sadly died recently) in his proofs of the existence of some of the sporadic finite simple groups.


Incidentally, the O'Nan simple group, which arises as a subgroup of $S\_{122760}$ is the only remaining sporaic group for which no computer-free existence proof has been found. Its existence can now be proved using versions of this algorithm in a few seconds on a laptop.


See the [Wikipedia article](https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm) for morec details and references.


