Complexity of permutation related problems Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there exists some $\pi\in G$ such that $\pi(u)=v$ where $\pi(u)$ means applying the permutation $\pi$ on $u$ in an expected way. 

Suppose further that $G$ is given, as the input, by a finite set $S$ of generators. What's the complexity of the problem? In particular, is it in NP?
Let $g_1, \ldots, g_k, g \in S_n$ where $S_n$ is the permutation group on $n$ elements. Testing whether $g \in \langle g_1, \ldots, g_k \rangle$ can be done in $\text{NC} \subseteq \text{P}$ by [1]. Let $u, v \in \Gamma^n$, then simply guess $g \in S_n$, test in polynomial time whether $g \in G$ and whether $g(u) = v$. This yields an $\text{NP}$ upper bound.

To complement this answer:


  Group membership was shown to belong to $\text{P}$ (Furst et al. 1980), then to
  $\text{NC}^3$ for abelian groups (McKenzie &amp; Cook 1987; Mulmuley
  1987), to $\text{NC}$ for nilpotent groups (Luks &amp; McKenzie 1988), solvable
  groups (Luks &amp; McKenzie 1988), groups with bounded non-abelian
  composition factors (Luks 1986), and finally all groups (Babai et al.
  1987). A similar complexity classification of  aperiodic monoids
  membership owes to (Beaudry 1988; Beaudry et al. 1992; Kozen 1977),
  who show that membership for any fixed aperiodic monoid variety is
  either in $\text{AC}^0$ , in $\text{P}$, in $\text{NP}$, or in $\text{PSPACE}$ (and complete for
  that class with very few exceptions).


[1] L. Babai, E. M. Luks &amp; A. Seress. Permutation groups in NC. Proc. $19^\text{th}$ annual ACM symposium on Theory of computing, pp. 409-420, 1987.