<p>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}$.</p>

<p>Reduction from GI: let $N = \binom{n}{2}$, and let $G \leq S_N$ be the induced action of $S_n$ on pairs. </p>

<p>$\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.</p>

CC BY-SA 3.0
2014-09-23T15:12:51.170Z
Combining my comment to Michael Blondin's answer with your answer, now I am afraid that I accidentally committed to _think_ GI is in P (and probably also in NC).
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T03:27:17.640Z
2014-09-23T03:27:17.640Z
Joshua Grochow
<p>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.</p>

<p>To complement this answer:</p>

<blockquote>
  <p>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).</p>
</blockquote>

<p><strong>[1]</strong> 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.</p>

CC BY-SA 3.0
2014-09-23T00:59:38.660Z
My answer was incorrect, and I deleted it (the subgroup which I denoted N in my answer was not normal in general).  I think the problem is in P (and probably also in NC), but I do not have a proof right now.
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T01:01:18.683Z
I don't see why your answer is incorrect. The permutation $\pi$ can indeed be constructed easily, then group membership where the groups are given as a list of generators is in NC by Babai, Luks & Seress 87.
Michael Blondin
CC BY-SA 3.0
2014-09-23T01:04:44.620Z
One choice for π can be constructed easily, but what should we do if this π does not belong to G?  Probably there is a way to find the right π from the beginning, but right now I do not see how to do this.
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T01:05:52.170Z
Oh, you are right. I will edit my answer back to the NP upper bound.
Michael Blondin
CC BY-SA 3.0
2014-09-23T01:06:48.797Z
Thanks for the edit, and sorry for causing confusion by my incorrect answer.
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T00:29:55.383Z
2014-09-23T05:01:07.577Z
2014-09-23T05:01:07.577Z
Michael Blondin
<p>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. </p>

<p>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?</p>

CC BY-SA 3.0
2014-09-21T23:03:49.157Z
What do you mean by a finite set of generators? How is it represented in the input?
R B
CC BY-SA 3.0
2014-09-22T10:41:27.167Z
I think an example is: two generators $S_1=(1 2)(3)$, $S_2=(1 3)(2)$ and $G$ is the group generated by $S_1$ and $S_2$.
maomao
CC BY-SA 3.0
2014-09-22T20:01:50.453Z
In general this problem would be NP-hard (probably this is already studied in some ref i am not aware of). Nevertheless the [Another Solution Problem](http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf) (related to sudoku game as well), might interest you
Nikos M.
CC BY-SA 3.0
2014-09-22T20:04:18.227Z
Moreover this is an inverse problem (which can be approached in a MAXENT way a-la Jaynes)
Nikos M.
CC BY-SA 3.0
2014-09-22T21:13:46.110Z
The question is not whether it is NP-hard, but whether it is in NP. The trivial upper bound is only PSPACE.
Emil Jeřábek
CC BY-SA 4.0
2022-10-25T20:20:52.960Z
Wouldn’t it be enough to test whether $v\circ u^{-1}\in G$?
Narek Bojikian
<cc.complexity-theory><graph-isomorphism><permutations>
Complexity of permutation related problems
user27313
# Complexity of permutation related problems

(Asked by: username_0 on 2014-09-21)

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?

**Tags:** cc.complexity-theory, graph-isomorphism, permutations
> **Comments:**
> **username_1**: What do you mean by a finite set of generators? How is it represented in the input?  
> **username_2**: I think an example is: two generators $S_1=(1 2)(3)$, $S_2=(1 3)(2)$ and $G$ is the group generated by $S_1$ and $S_2$.  
> **username_3**: In general this problem would be NP-hard (probably this is already studied in some ref i am not aware of). Nevertheless the [Another Solution Problem](http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf) (related to sudoku game as well), might interest you  
> **username_3**: Moreover this is an inverse problem (which can be approached in a MAXENT way a-la Jaynes)  
> **username_4**: The question is not whether it is NP-hard, but whether it is in NP. The trivial upper bound is only PSPACE.  
> **username_5**: Wouldn’t it be enough to test whether $v\circ u^{-1}\in G$?  

---

## 2 answers

### Answer by username_8 on 2014-09-23. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_7**: My answer was incorrect, and I deleted it (the subgroup which I denoted N in my answer was not normal in general).  I think the problem is in P (and probably also in NC), but I do not have a proof right now.  
> **username_8**: I don't see why your answer is incorrect. The permutation $\pi$ can indeed be constructed easily, then group membership where the groups are given as a list of generators is in NC by Babai, Luks & Seress 87.  
> **username_7**: One choice for π can be constructed easily, but what should we do if this π does not belong to G?  Probably there is a way to find the right π from the beginning, but right now I do not see how to do this.  
> **username_8**: Oh, you are right. I will edit my answer back to the NP upper bound.  
> **username_7**: Thanks for the edit, and sorry for causing confusion by my incorrect answer.  

---

### Answer by username_6 on 2014-09-23. Score: 10

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.

> **Comments:**
> **username_7**: Combining my comment to Michael Blondin's answer with your answer, now I am afraid that I accidentally committed to _think_ GI is in P (and probably also in NC).  

---

