13
$\begingroup$

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?

$\endgroup$
  • 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 supports Monica Sep 22 '14 at 21:13
11
$\begingroup$

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.

$\endgroup$
  • 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
10
$\begingroup$

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.

$\endgroup$
  • 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
-2
$\begingroup$

Despite my comments, i will also add an answer.

In the case the two given vectros are known to be a permutation of one another (and the permutation is known/assumed to be in the given group $G$). Then the permutation which transforms $v \to u$ can be found in linear time as such:

  1. Align the 2 vectors one under the other

  2. The permutation is found by starting from the 1st element of $v$ which is transformed into the 1st element of $u$

  3. Get the position of the element in previous step (of $u$ into $v$) and repeat step (2), then that is the 2nd element of the permutation and so on, until, all the elements are traversed.

When whether the two vectors are not known to be positively the permutation of each other (or for more general cases where there can be multiple transformations, as for example a sudoku game), check the Another Solution Problem which is in general NP-hard. This requirs to use some symmetry transformations (e.g permutations) which satisfy the constraints of a given problem to generate another solution of the problem given an initial solution.

Furthermore this is part of the problems known as Inverse Problems (a-la Jaynes)

$\endgroup$
  • 1
    $\begingroup$ There is no reason why the permutation found this way should be in the given group $G$. $\endgroup$ – Emil Jeřábek supports Monica Sep 22 '14 at 20:52
  • $\begingroup$ @EmilJeřábek, hmm, missed this part, however this part of the answer assumes this is so (for illustration puproses of a linear algorithm), wil edit the answer $\endgroup$ – Nikos M. Sep 22 '14 at 20:54
  • $\begingroup$ Checking whether there exists some permutation mapping $u$ to $v$ (as well as countructing such a permutation), is trivial: just count how many times each symbol occurs in both words. $\endgroup$ – Emil Jeřábek supports Monica Sep 22 '14 at 21:13
  • 1
    $\begingroup$ If $u$ is not a permutation of $v$, then the answer to the instance is no, otherwise such a permutation $\pi$ can be computed in logspace. However, it does not solve the problem as $\pi$ might not be in $G$. With your current assumptions, you assume every instance is a yes-instance, which may then be trivially decided in constant time. I'm not sure how you answer the question. $\endgroup$ – Michael Blondin Sep 23 '14 at 5:23
  • 2
    $\begingroup$ You gave no evidence for the claim that the problem is NP-hard, or that it has anything to do with ASP. By Joshua Grochow’s answer, the problem is not NP-hard unless the polynomial hierarchy collapses to the second level (AM = coAM, to be precise). $\endgroup$ – Emil Jeřábek supports Monica Sep 23 '14 at 18:17

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.