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?

  • 3
    $\begingroup$ What do you mean by a finite set of generators? How is it represented in the input? $\endgroup$
    – R B
    Sep 21, 2014 at 23:03
  • $\begingroup$ 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$. $\endgroup$
    – maomao
    Sep 22, 2014 at 10:41
  • $\begingroup$ 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 (related to sudoku game as well), might interest you $\endgroup$
    – Nikos M.
    Sep 22, 2014 at 20:01
  • $\begingroup$ Moreover this is an inverse problem (which can be approached in a MAXENT way a-la Jaynes) $\endgroup$
    – Nikos M.
    Sep 22, 2014 at 20:04
  • $\begingroup$ The question is not whether it is NP-hard, but whether it is in NP. The trivial upper bound is only PSPACE. $\endgroup$ Sep 22, 2014 at 21:13

2 Answers 2


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.

  • 1
    $\begingroup$ 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. $\endgroup$ Sep 23, 2014 at 0:59
  • $\begingroup$ 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. $\endgroup$ Sep 23, 2014 at 1:01
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 23, 2014 at 1:04
  • $\begingroup$ Oh, you are right. I will edit my answer back to the NP upper bound. $\endgroup$ Sep 23, 2014 at 1:05
  • $\begingroup$ Thanks for the edit, and sorry for causing confusion by my incorrect answer. $\endgroup$ Sep 23, 2014 at 1:06

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.

  • 1
    $\begingroup$ 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). $\endgroup$ Sep 23, 2014 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.