For the [permutation group isomorphism](https://cstheory.stackexchange.com/questions/32783/quasi-polynomial-time-algorithm-for-permutation-group-isomorphism) problem, a permutational isomorphism between two permutation groups is sought. A closely related but seemingly easier problem arises, if an isomorphism between the groups is already fixed, and only a compatible (bijective) mapping of the sets where the groups act must be computed. Instead of fixing an isomorphism between the groups, we can also say that we have just a single group acting on two different sets.


This problem seems to be easier (than the permutation group isomorphism problem), because it seems to allow to directly exploit the fact that any group of size $n$ has a generator set of size at most $\log\_2 n$. Such a generator set allows a construction similar to a [Cayley graph](https://en.wikipedia.org/wiki/Cayley_graph), such that all that remains is to compute an isomorphism of the corresponding graphs. But I haven't found a suitable data structure for representing the automorphisms of such graphs yet, so I'm stuck at that point.


Because the problem doesn't feel too difficult, I wonder whether it has been solved already. An algorithm with run time polynomial in the size of the set and the size of the group (i.e. exponential in the size of a minimal generator set) would qualify as a solution, in the context of this question. 



Group acting on two different sets, can isomorphisms be computed efficiently?
I'm still not sure in what form your input is given. I'll assume you have permutations $\lbrace g\_1,\ldots,g\_k\rbrace$ generating $G$, and permutations $\lbrace h\_1,\ldots,h\_k\rbrace$ generating $H$, and you know there is an isomorphism $\phi:G\to H$ defined by $\phi(g\_j)=h\_j$ for each $j$. Now you want to find a conjugacy in $S\_n$ that implements that isomorphism, i.e. an element $\ell\in S\_n$ such that $g\_j^\ell=h\_j$ for all $j$, or to prove that there is none.


If this is the question, then the question seems to be identical to [**this one**](https://mathoverflow.net/questions/162428/the-simultaneous-conjugacy-problem-in-the-symmetric-group-s-n/162453#162453). You will see that I gave an algorithm there with time requirements $O(n^2k)$.


If your input doesn't consist of permutations, something else is needed.


