I want to consider the following problem, which generalises the decision problem to decide if a given finite permutation group is a Frobenius group:
Given a finite permutation group in terms of its generators and a parameter $k$, decide if every element fixes at most $k$ points.
What do you know about the complexity of this decision problem, is it in $P$ or in $NP$? Is it in $P$ if we fix $k$?
As I said in my comment, this problem is easily seen to be in P for fixed $k$, because we can compute all $(k+1)$-point stabilizers in polynomial time.
So let's assume that $k$ is part of the input.
I am not sure about NP, but the opposite question, does there exist a non-identity permutation fixing at least $k+1$ points is clearly in NP, because we can answer the question in the affirmative by exhibiting such a permutation, and membership testing in $G$ is polynomial-time.
Nobody has any idea how to go about proving apparently hard problems in algorithmic permutation group theory are not in P, so it is very unlikely that it will be proved that this problem is not in P any time soon. But if I had to take a bet on it I would go for not in P.
Here is an example which I think might be difficult. Suppose $|X| = 2n$ is even, and let $U$ be an elementary abelian subgroup of order $2^n$ of ${\rm Sym}(X)$ with $n$ orbits, each of length $2$.
Now let $G$ be a subgroup of $U$ with say $n/2$ randomly chosen generators. What is the largest number of fixed points of a nontrivial element of $G$?
This example has been considered in other algorithmic contexts. For example it is not known whether the normalizer of $G$ in ${\rm Sym}(X)$ can be computed even in simply exponential time.
