Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 & Cook 1987; Mulmuley 1987), to $\text{NC}$ for nilpotent groups (Luks & McKenzie 1988), solvable groups (Luks & 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 & A. Seress. Permutation groups in NC. Proc. $19^\text{th}$ annual ACM symposium on Theory of computing, pp. 409-420, 1987.
Your problem is known as ($\Gamma$-)string $G$-isomorphism. It is in a fairly narrow class of problems around Graph Isomorphism: it's at least as hard as GI, and is in $\mathsf{NP} \cap \mathsf{coAM}$.
Reduction from GI: let $N = \binom{n}{2}$, and let $G \leq S_N$ be the induced action of $S_n$ on pairs.
$\mathsf{coAM}$ protocol: Arthur randomly chooses an element of $G$ (I'm not sure this can be done exactly uniformly, but I think the known algorithms get close enough to uniform for this result) and applies it to both $u$ and $v$. With probability 1/2 he swaps $u$ and $v$, then presents them to Merlin and asks which was which.
