# Complexity of permutation related problems

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?

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

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).

 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.

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

• 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). Sep 23, 2014 at 15:12