<p>The answer is basically yes, if we take into account the hidden assumption that the degree of the group is at most $n$. More precisely, let $G_1, G_2$ with $|G_1|=| G_2|=n$ be finite permutation groups acting on a set $\Omega$. Then existence of a permutational isomorphism between $G_1$ and $G_2$ can be checked in time $n^{\log_2 n} \cdot {\max(|\Omega|,n)}^{O(1)}$.</p>

<p>As suggested in the question, a permutation group has a base and corresponding <a href="https://en.wikipedia.org/wiki/Strong_generating_set" rel="nofollow noreferrer">strong generating set</a> (SGS) of size at most $\log_2 n$, and both can be computed in time polynomial in $n$. But this isn't even needed, any generating set of size at most $\log_2 n$ is enough.</p>

<p>After computing such a generating set for $G_1$, the algorithm simply maps successively each element of the generating set to an element of $G_2$, and checks for each such mapping whether it leads to an isomorphism of $G_1$ and $G_2$. For those who do, the algorithm then checks whether there is a permutation of $\Omega$ inducing that isomorphism (for example by a <a href="https://mathoverflow.net/questions/162428/the-simultaneous-conjugacy-problem-in-the-symmetric-group-s-n/162453#162453">canonical labeling technique</a>, which is closely related to a <a href="https://gentzen.wordpress.com/2015/11/15/a-canonical-labeling-technique-by-brendan-mckay-and-isomorphism-testing-of-deterministic-finite-automata/" rel="nofollow noreferrer">similar technique for deterministic finite automata</a>, but <a href="https://mathoverflow.net/a/222511">more group theoretic methods</a> also work). Those checks can be done in time ${\max(|\Omega|,n)}^{O(1)}$, and because there are at most $n^{\log_2 n}$ such mappings, and every isomorphism between $G_1$ and $G_2$ is determined by such a mapping, the above time bound follows.</p>

CC BY-SA 3.0
2016-02-11T21:23:07.987Z
Obviously you know what you were asking about, but it's worth pointing out that most people, when talking about algorithms on permutation groups, want the running time expressed in terms of the size of the input, which is typically a list of permutations. That is, typically in permutation groups, n is used to denote the degree of the groups, which can be exponentially smaller than their order. As you'll see in the final section of Babai's recent paper, it remains open whether there is a quasi-poly (in the degree) algorithm for perm iso of perm groups.
Joshua Grochow
CC BY-SA 3.0
2016-02-12T08:35:59.947Z
@JoshuaGrochow I wondered whether permutation group isomorphism is more difficult than group isomorphism, so I tried to come up with an answerable question by staying close to the group isomorphism setup. And I wanted a problem that is many-one reducible to GI, because the ultimate goal was/is to find sources of hard GI instances. Knowing possible sizes of (strong) generating sets was also important. After learning this from [Lecture 2, Algebra and Computation by V. Arvind](https://www.imsc.res.in/~arvind/notes.pdf), I started to write this answer, which turned out to be nearly trivial.
Thomas Klimpel
CC BY-SA 3.0
2016-02-12T20:51:10.110Z
Seems reasonable. (Just wanted to point out that "finding a quasi-polynomial-time algorithm for permutational isomorphism of permutation groups," in the usual terminology, is still an interesting open question.)
Joshua Grochow
CC BY-SA 3.0
2016-02-11T08:32:36.327Z
2016-02-11T08:32:36.327Z
2017-04-13T12:57:54.777Z
Thomas Klimpel
<p>Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism.</p>

<p>My hope for such an algorithm comes from reading a <a href="https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/" rel="nofollow noreferrer">blog post on the group isomorphism problem</a> and its comments. Because any group of size $n$ has a generator set of size at most $\log_2 n$, maybe a permutation group will even have a strong generator set of size at most $\log_2 n$ (and hopefully that would already be sufficient for a quasi-polynomial algorithm). The comments mention <a href="http://people.cs.uchicago.edu/~laci/papers/soda11.pdf" rel="nofollow noreferrer">two</a> <a href="http://people.cs.uchicago.edu/~laci/papers/icalp12.pdf" rel="nofollow noreferrer">papers</a> that relate the complexity of the  problem of permutational isomorphism of permutation groups to the complexity of the problem of isomorphism of semisimple groups, and also mention earlier work on the permutational isomorphism problem.</p>

<hr>

<p>A <a href="https://mathoverflow.net/questions/215464/can-every-permutation-group-be-realized-as-the-automorphism-group-of-a-graph-ac#comment532361_215472">comment by Ben Barber</a> on a related question indicates that permutation group isomorphism can be reduced to graph isomorphism, which is not really surprising, but nice to know nevertheless.</p>

<cc.complexity-theory><graph-isomorphism><gr.group-theory>
Quasi-polynomial time algorithm for permutation group isomorphism
Thomas Klimpel
# Quasi-polynomial time algorithm for permutation group isomorphism

(Asked by: username_0 on 2015-10-11)

Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism.

My hope for such an algorithm comes from reading a [blog post on the group isomorphism problem](https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/) and its comments. Because any group of size $n$ has a generator set of size at most $\log\_2 n$, maybe a permutation group will even have a strong generator set of size at most $\log\_2 n$ (and hopefully that would already be sufficient for a quasi-polynomial algorithm). The comments mention [two](http://people.cs.uchicago.edu/~laci/papers/soda11.pdf) [papers](http://people.cs.uchicago.edu/~laci/papers/icalp12.pdf) that relate the complexity of the problem of permutational isomorphism of permutation groups to the complexity of the problem of isomorphism of semisimple groups, and also mention earlier work on the permutational isomorphism problem.

---

A [comment by Ben Barber](https://mathoverflow.net/questions/215464/can-every-permutation-group-be-realized-as-the-automorphism-group-of-a-graph-ac#comment532361_215472) on a related question indicates that permutation group isomorphism can be reduced to graph isomorphism, which is not really surprising, but nice to know nevertheless.

**Tags:** cc.complexity-theory, graph-isomorphism, gr.group-theory


---

## 1 answers

### Answer by username_0 on 2016-02-11. Score: 2 | Accepted answer

The answer is basically yes, if we take into account the hidden assumption that the degree of the group is at most $n$. More precisely, let $G\_1, G\_2$ with $|G\_1|=| G\_2|=n$ be finite permutation groups acting on a set $\Omega$. Then existence of a permutational isomorphism between $G\_1$ and $G\_2$ can be checked in time $n^{\log\_2 n} \cdot {\max(|\Omega|,n)}^{O(1)}$.

As suggested in the question, a permutation group has a base and corresponding [strong generating set](https://en.wikipedia.org/wiki/Strong_generating_set) (SGS) of size at most $\log\_2 n$, and both can be computed in time polynomial in $n$. But this isn't even needed, any generating set of size at most $\log\_2 n$ is enough.

After computing such a generating set for $G\_1$, the algorithm simply maps successively each element of the generating set to an element of $G\_2$, and checks for each such mapping whether it leads to an isomorphism of $G\_1$ and $G\_2$. For those who do, the algorithm then checks whether there is a permutation of $\Omega$ inducing that isomorphism (for example by a [canonical labeling technique](https://mathoverflow.net/questions/162428/the-simultaneous-conjugacy-problem-in-the-symmetric-group-s-n/162453#162453), which is closely related to a [similar technique for deterministic finite automata](https://gentzen.wordpress.com/2015/11/15/a-canonical-labeling-technique-by-brendan-mckay-and-isomorphism-testing-of-deterministic-finite-automata/), but [more group theoretic methods](https://mathoverflow.net/a/222511) also work). Those checks can be done in time ${\max(|\Omega|,n)}^{O(1)}$, and because there are at most $n^{\log\_2 n}$ such mappings, and every isomorphism between $G\_1$ and $G\_2$ is determined by such a mapping, the above time bound follows.

> **Comments:**
> **username_1**: Obviously you know what you were asking about, but it's worth pointing out that most people, when talking about algorithms on permutation groups, want the running time expressed in terms of the size of the input, which is typically a list of permutations. That is, typically in permutation groups, n is used to denote the degree of the groups, which can be exponentially smaller than their order. As you'll see in the final section of Babai's recent paper, it remains open whether there is a quasi-poly (in the degree) algorithm for perm iso of perm groups.  
> **username_0**: @JoshuaGrochow I wondered whether permutation group isomorphism is more difficult than group isomorphism, so I tried to come up with an answerable question by staying close to the group isomorphism setup. And I wanted a problem that is many-one reducible to GI, because the ultimate goal was/is to find sources of hard GI instances. Knowing possible sizes of (strong) generating sets was also important. After learning this from [Lecture 2, Algebra and Computation by V. Arvind](https://www.imsc.res.in/~arvind/notes.pdf), I started to write this answer, which turned out to be nearly trivial.  
> **username_1**: Seems reasonable. (Just wanted to point out that "finding a quasi-polynomial-time algorithm for permutational isomorphism of permutation groups," in the usual terminology, is still an interesting open question.)  

---

