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 '14 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 '14 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 '14 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 '14 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$ – Emil Jeřábek Sep 22 '14 at 21:13

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.

| cite | improve this answer | |
  • 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$ – Tsuyoshi Ito Sep 23 '14 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$ – Michael Blondin Sep 23 '14 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$ – Tsuyoshi Ito Sep 23 '14 at 1:04
  • $\begingroup$ Oh, you are right. I will edit my answer back to the NP upper bound. $\endgroup$ – Michael Blondin Sep 23 '14 at 1:05
  • $\begingroup$ Thanks for the edit, and sorry for causing confusion by my incorrect answer. $\endgroup$ – Tsuyoshi Ito Sep 23 '14 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.

| cite | improve this answer | |
  • 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$ – Tsuyoshi Ito Sep 23 '14 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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