14

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?

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
user27313
  • 143
  • 4

2 Answers2

12

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.

Michael Blondin
  • 2,582
  • 21
  • 22
  • 1
    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 Sep 23 '14 at 00:59
  • 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 Sep 23 '14 at 01:01
  • 1
    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 Sep 23 '14 at 01:04
  • Oh, you are right. I will edit my answer back to the NP upper bound. – Michael Blondin Sep 23 '14 at 01:05
  • Thanks for the edit, and sorry for causing confusion by my incorrect answer. – Tsuyoshi Ito Sep 23 '14 at 01:06
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.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 1
    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 Sep 23 '14 at 15:12