<p>As far as I can tell, if you ask simply about the consequences of the mere fact (as a black box) that GI is in QP, I think the answer is very little. The one thing I can think of, which is not a theorem but a consequence for research directions, is to <em>Group</em> Isomorphism. Since GroupIso reduces to GI and we don't even know if GroupIso is in P, putting GroupIso into P can be seen as an important obstacle to putting GI into P (if you think the latter might be the case). </p>

<p>However, since the trivial algorithm for GroupIso is $n^{\log n + O(1)}$, back when the complexity of GI was up at $2^{\tilde O(\sqrt{n})}$, we had a long way to go in improving the complexity of GI before GroupIso became an <em>immediately relevant</em> obstacle to putting GI into P. But if GI is in QP, then GroupIso becomes a much more relevant obstacle to further improvements in GI. (Of course, the exponent of the exponent in the quasi-polynomial is still a potentially relevant gap, but the gap becomes a <em>lot</em> smaller when GI is in QP.)</p>

CC BY-SA 3.0
2017-01-10T21:43:21.247Z
It appears that we are not able to improve on much weaker upper bound of testing the isomorphism of projective planes ($n^{O(\log \log n)}$) . See http://cstheory.stackexchange.com/questions/34773/testing-isomorphism-of-projective-planes
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-01-10T22:21:20.120Z
@MohammadAl-Turkistany: Yes, but then my same argument applies: if GI is "way" up at quasipoly, then ProjPlaneIso is very far from being an obstacle to putting GI into P. Once GI is in time $n^{O(\log \log n)^c}$ for some $c$, then ProjPlaneIso would become a relevant obstacle. So, at the moment, it would seem that GroupIso is the more immediate obstacle - maybe someday ProjPlaneIso will be...
Joshua Grochow
CC BY-SA 3.0
2017-01-10T23:33:57.200Z
@JoshuaGrochow Would you agree with me that the approach taken by François Le Gall and David J. Rosenbaum in [On the Group and Color Isomorphism Problems](https://arxiv.org/abs/1609.08253) makes sense? Or at least that they do treat some questions that could come up after gaining a basic understanding of László Babai’s result?
Thomas Klimpel
CC BY-SA 3.0
2017-01-11T06:31:02.153Z
@ThomasKlimpel: I agree that their paper makes sense, though I don't yet see how to take advantage of their insights (despite understanding most of Babai's proof).
Joshua Grochow
CC BY-SA 3.0
2017-01-16T10:00:18.267Z
Don't you believe that GI in QP would ultimately lead to placing GI in limited nondeterminism class such as $\beta_k P $?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-01-10T18:34:52.340Z
2017-01-10T18:34:52.340Z
Joshua Grochow
<p>Concerning the last question: the time hierarchy theorem immediately implies that QP has no complete problems under polynomial-time many-one or Turing reductions. (On the other hand, every problem save $\varnothing$ and $\Sigma^*$ is QP-hard under <em>quasi-polynomial</em> reductions.) Thus, assuming Babai’s result is correct, GI is <em>not</em> QP-hard.</p>

CC BY-SA 3.0
2017-01-30T12:42:55.657Z
2017-01-30T12:42:55.657Z
Emil Jeřábek
<blockquote>
  <p>What would be the complexity theoretic consequences of a quasi-polynomial time algorithm for the Graph Isomorphism problem?</p>
</blockquote>

<p>More or less similar to the consequences of the deterministic polynomial time algorithm for primality testing, the deterministic polynomial time algorithm for linear programming, and the other case where practically efficient (randomised) algorithms (with rare pathological examples where the algorithm became inefficient) were know and in use for a long time. It confirms the conjecture that practical efficiency is a good indicator for the existence of deterministic theoretical algorithms overcoming the issues of the rare pathological examples.</p>

<blockquote>
  <p>Would a quasi-polynomial time algorithm for GI refute any famous conjectures in complexity theory?</p>
</blockquote>

<p>No, the conjectures rather go to the opposite site, namely that GI is in P. Since GI is in NP, it won't be possilbe to refute this type of conjecture anytime soon.</p>

<blockquote>
  <p>Can we efficiently reduce Minimum Dominating Set in Tournaments problem to GI?</p>
</blockquote>

<p>Minimum Dominating Set is not an isomorphism problem, hence there is no reason why it should be expected to be reducible to GI.</p>

<blockquote>
  <p>Is there any conjecture ruling out GI being hard for QP?</p>
</blockquote>

<p>We don't even know how to reduce the string isomorphism problem to GI, and this is at least an isomorphism problem. Babai's proof showed that string isomorphism was in QP, so ... And what is being hard for QP even supposed to mean? Hard under polynomial time reductions?</p>

<hr>

<p>From the introduction of <a href="https://arxiv.org/abs/1609.08253" rel="nofollow noreferrer">On the Group and Color Isomorphism Problems</a> by François Le Gall and David J. Rosenbaum</p>

<blockquote>
  <p>The complexity of isomorphism testing problems is worthy of study both because they are fundamental computational questions and also because many of them are not known to be in P, but nevertheless appear to be easier than the NP-complete problems. The most heavily studied of these is the graph isomorphism problem.</p>
</blockquote>

<p>I believed I knew that all isomorphism testing problems of finite structures can be reduced to the graph isomorphism problem. Hence I believed that graph isomorphism was the "correct general" isomorphism problem to rule them all. The string isomorphism problem used in Babai's paper revealed that my belief was not fully justified, since it is still unknown whether the string isomorphism problem can be reduced to the graph isomorphism problem. Hence the generalized graph isomorphism problem $\mathsf{GI}^*$ and the generalized group isomorphism problem $\mathsf{GrI}^*$ are defined (in the above paper, but the authors rightly wonder why nobody did it before), which add the missing pieces from the string isomorphism problem. (And color isomorphism problem is just a different name for the string isomorphism problem. The name color automorphism problem goes back to the initial papers of Babai and Luks, the name string isomorphism occurs later in their paper on canonical labeling.)</p>

<p>Since Babai's algorithm was a quasi-polynomial time algorithm for the string isomorphism problem (i.e. for $\mathsf{GI}^*$), the consequence was that isomorphism testing for most types of finite structures should be expected to be quite doable. One application of such isomorphism testing is to list all different types of non-isomorphic structures with certain properties within a given range. Well, actually that application works much better with algorithms for canonisation (as opposed to mere isomorphism testing of two given structures), but the additional slowdown wouldn't change the <em>principal</em> polynomial or quasi-polynomial time bound for those problems.</p>

<hr>

<p><strong>Edit:</strong> This answer was given in the context of the retraction of Babai's result, before he announced a fix. It suggests that the slight generalization of the graph isomorphism problem suggested by the string isomorphism problem is the really important problem. The implicit expectation here is that any <em>reasonable</em> algorithm for the graph isomorphism problem will lead to a similar algorithm for the generalized graph isomorphism problem. The generalized problem is polynomial time equivalent to the <a href="https://groupprops.subwiki.org/wiki/Set-stabilizer_problem" rel="nofollow noreferrer">set-stabilizer problem</a>, the <a href="https://groupprops.subwiki.org/wiki/Group_intersection_problem" rel="nofollow noreferrer">group intersection problem</a>, the coset intersection problem, the <a href="https://groupprops.subwiki.org/wiki/Set_transporter_problem" rel="nofollow noreferrer">set transporter problem</a>, ... The idea behind this expectation is that the generalized problem will occur in the <em>recursive part</em> of any reasonable algorithm, so it has to be addressed anyway. (And it is quite possible the the generalized problem is polynomial time equivalent to graph isomorphism.)</p>

<p>Now Joshua Grochow's comments indicates that I wasn't successful in explaining the conceptual importance of the missing pieces from the string isomorphism problem. For infinite structures, it may be easier to appreciate that a valid isomorphism should not just preserve the given structure, but also belong to an appropriate category of functions (for example the category of continuous functions). For finite structures, the analogous phenomenon mostly occurs for quotient structures, where the appropriate category of functions should be compatible with the given quotients. The Johnson stuff is a typical example of such quotients, for example partition logic is working over the two element subsets of some base set. Also note that restricting the allowed category for the isomorphisms often makes the isomorphism testing problem easier, and that this might be the really crucial point for the importance of the generalized problem.</p>

<p>The problem with generalizations of the graph isomorphism problem is where to stop. Why not generalize so far as to encompass the permutation group isomorphism problem? This question is really hard, since many non-trivial results for graph isomorphism will probably carry over to permutation group isomorphism as well. But here it feels more reasonable to treat computational permutation group theory as a subject in its own right, even if it has indeed close connection to the graph isomorphism problem. </p>

CC BY-SA 3.0
2017-01-11T06:29:45.453Z
First, as far as I understand it, string iso = color iso; what "artificial restrictions" do you mean? Second, the well-known result about isomorphism of all finite structures reducing to GI is a statement about finite structures definable in first-order logic. String isomorphism/color isomorphism doesn't fall into that class, since it asks not just whether two strings are isomorphic as first-order structures, but whether there is a first-order isomorphism between two strings where the isomorphism lies *in a given subgroup of $S_n$*.
Joshua Grochow
CC BY-SA 3.0
2017-01-11T08:15:16.727Z
@JoshuaGrochow For color iso, the colors are just arbitrary numbers (wlog restricted to [n]). For string iso, the strings are given over a fixed finite alphabet. I thought it was a binary alphabet, but I misremembered this. I just remembered that I was initially confused whether color iso was just a different name for string iso. So when I decided to read that paper after Laszlo retracted his claim, it felt like a difference to me. Maybe it really is a difference, because "over a finite alphabet" communicates "fix your favorite finite alphabet, it won't make any difference". Which is true.
Thomas Klimpel
CC BY-SA 3.0
2017-01-14T16:01:08.393Z
Even if they are making this distinction, the two problems you state are equivalent: over a fixed finite alphabet, simply use substrings of length $\log n$ to encode colors from $[n]$, and then change your group so that it only ever moves these substrings as a whole.
Joshua Grochow
CC BY-SA 3.0
2017-01-30T10:23:25.637Z
@JoshuaGrochow This is exactly what I meant by *it won't make any difference". Which is true.* I now tried to address your "String isomorphism/color isomorphism doesn't fall into that class" comment. I enjoyed learning some lessons from Andreas Blass and Yuri Gurevich on the way, who also try to focus on conceptual points. I am happy that Babai fixed his algorithm now, so that I feel no obligation (or pressure) to investigate whether graph isomorphism and string isomorphism are polynomial time equivalent. (Which was the context why I wrote that answer.)
Thomas Klimpel
CC BY-SA 3.0
2017-01-30T10:25:49.357Z
I am confused why you compare progress on GI with derandomization results.
Sasho Nikolov
CC BY-SA 3.0
2017-02-01T22:15:20.900Z
@SashoNikolov Because nobody plans to replace the existing practically efficient algorithms with the new theoretically efficient algorithm. The entire first part of this answer is just meant to spell out the obvious.
Thomas Klimpel
CC BY-SA 3.0
2017-01-06T20:00:29.810Z
2017-01-30T10:33:38.063Z
2017-01-30T10:33:38.063Z
Thomas Klimpel
<p>The <a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow noreferrer">Graph Isomorphism problem</a> (GI) is arguably 
the best known candidate for an <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">NP-intermediate</a> problem. 
The best known algorithm is sub-exponential algorithm 
with run-time $2^{O(\sqrt{n \log n})}$. 
It is known that GI is not $\mathsf{NP}$-complete unless 
the <a href="https://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="nofollow noreferrer">polynomial hierarchy</a> collapses. </p>

<blockquote>
  <p>What would be the complexity theoretic consequences of a quasi-polynomial time algorithm for the Graph Isomorphism problem?<br>
  Would a quasi-polynomial time algorithm for GI refute any famous conjectures in complexity theory?</p>
</blockquote>

<hr>

<p>Other similar problems like 
Minimum Dominating Set in Tournaments problem, 
Group Isomorphism problem, and 
Tournament Isomorphism problem 
have quasi-polynomial time (<a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp" rel="nofollow noreferrer">QP</a>) algorithms. 
The later two problems are polynomial-time reducible to GI.</p>

<blockquote>
  <p>Can we efficiently reduce Minimum Dominating Set in Tournaments problem to GI?<br>
  Is there any conjecture ruling out GI being hard for QP?</p>
</blockquote>

<p><strong>Update (2015-12-14)</strong>: Babai has <a href="http://arxiv.org/abs/1512.03547" rel="nofollow noreferrer">posted a preliminary draft paper</a> on arXiv for his quasipolynomial-time algorithm for GI.</p>

<p><strong>Update (2017-01-04)</strong>: Babai <a href="http://people.cs.uchicago.edu/~laci/update.html" rel="nofollow noreferrer">retracted</a> the claim that the algorithm is in quasipolynomial time, according to the new analysis the algorithm is in subexponential time $\exp \exp(\tilde{O}(\sqrt{\lg n}))$ which is inside $2^{n^{o(1)}}$.</p>

<p><strong>Update (2017-01-09)</strong>: Babai <a href="http://people.cs.uchicago.edu/~laci/update.html" rel="nofollow noreferrer">reinstated</a> the quasipolynomial time claim, replacing the offending procedure with a more efficient one.</p>

CC BY-SA 3.0
2013-11-25T14:16:01.120Z
Are there complexity-theoretic conjectures ruling out polynomial time algorithms?
usul
CC BY-SA 3.0
2013-11-25T15:01:07.247Z
I do not know. I guess it is possible that ruling out Quasi-PTIME algorithms would require more "natural" and hence weaker conjectures.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-25T15:08:20.450Z
I think many people do think it has a polynomial time algorithm, and AFAIK such an algorithm would not have any complexity theoretic consequences.
Huck Bennett
CC BY-SA 3.0
2013-11-25T17:50:30.430Z
@HuckBennett Is there any justification for this belief?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-25T18:28:54.343Z
@MohammadAl-Turkistany: Look at Scott's comment #13 here: http://www.scottaaronson.com/blog/?p=690.
Huck Bennett
CC BY-SA 3.0
2013-11-25T20:14:55.893Z
@HuckBennett A counter argument is that IF is in NP $\cap$ CoNP while GI is not known to be in CoNP.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-26T03:22:58.037Z
Also, I think there are many people who believe GI does *not* have a poly-time algorithm. For example, in Babai's 1995 survey (Handbook of Combinatorics vol. II) he says "None of the problems mentioned in this section [including GI], with the possible exception of isomorphism of groups given by a Cayley table, is expected to have polynomial time solution."
Joshua Grochow
CC BY-SA 3.0
2013-11-26T03:26:38.957Z
@MohammadAl-Turkistany: Why do you guess that ruling out quasi-poly algorithms would require "more 'natural' and hence weaker conjectures"? It seems that by definition ruling out quasi-poly algorithms requires a *stronger* conjecture than ruling out poly-time algorithms. As for naturality, I have no feeling either way for one lending itself to more "naturality" than the other; do you have some intuition for this?
Joshua Grochow
CC BY-SA 3.0
2013-11-26T07:10:43.153Z
My intuition is that we have natural problems such as dominating set in tournaments which has trivial and natural quasi-polynomial time algorithm. So, I thought ruling out quasi-polynomial time algorithms for GI would require some natural conjecture that uses a natural characterization of quasi-polynomial time algorithms. So, all depends on what natural means.  :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-26T07:21:27.363Z
@HuckBennett Another argument, we do have efficient quantum algorithm for IF while we are not able to find any polynomial time quantum algorithm for GI.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-26T15:32:19.597Z
This isn't quite what you're asking for, but it's the best I know of: Group Isomorphism has a natural and easy quasi-polynomial-time algorithm, but there is provably no $\mathsf{AC}^0$ reduction from GI to GroupIso: http://eccc.hpi-web.de/report/2010/117/. A formally easier question than what you ask, but still wide open, is to prove that there is no poly-time reduction from GI to GroupIso.
Joshua Grochow
CC BY-SA 3.0
2015-09-02T13:10:09.010Z
I am aware that GI is not known to be hard for $P$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-11-04T06:39:55.033Z
After two years I believe we have an answer. Laszlo Babai has proved that GI has a quasi polynomial time algorithm. Source: https://lucatrevisan.wordpress.com/2015/11/03/laci-babai-and-graph-isomorphism/
user3415207
CC BY-SA 3.0
2015-11-05T00:01:32.000Z
related: [GLL post](https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/) about Laszlo Babai's talk next week about GI being in QP.
Kaveh
CC BY-SA 3.0
2015-11-09T18:11:57.840Z
http://people.cs.uchicago.edu/~laci/quasipoly.html
Kaveh
CC BY-SA 3.0
2015-11-11T14:18:29.487Z
@user3415207 Not an answer to this here question, though.
Raphael
CC BY-SA 3.0
2017-01-04T21:46:37.430Z
@user3415207 [Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.
Raphael
CC BY-SA 3.0
2017-01-11T15:11:16.957Z
@Raphael ... and Babai restored his claim (same link as yours).
Danny
CC BY-SA 3.0
2017-01-11T17:04:55.790Z
@Danny Exciting times!
Raphael
<cc.complexity-theory><ds.algorithms><graph-theory><graph-isomorphism>
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
Mohammad Al-Turkistany
# Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

(Asked by: username_0 on 2013-11-25)

The [Graph Isomorphism problem](https://en.wikipedia.org/wiki/Graph_isomorphism_problem) (GI) is arguably
the best known candidate for an [NP-intermediate](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc) problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$.
It is known that GI is not $\mathsf{NP}$-complete unless
the [polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy) collapses.

> What would be the complexity theoretic consequences of a quasi-polynomial time algorithm for the Graph Isomorphism problem?  
> Would a quasi-polynomial time algorithm for GI refute any famous conjectures in complexity theory?

---

Other similar problems like
Minimum Dominating Set in Tournaments problem,
Group Isomorphism problem, and
Tournament Isomorphism problem
have quasi-polynomial time ([QP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp)) algorithms.
The later two problems are polynomial-time reducible to GI.

> Can we efficiently reduce Minimum Dominating Set in Tournaments problem to GI?  
> Is there any conjecture ruling out GI being hard for QP?

**Update (2015-12-14)**: Babai has [posted a preliminary draft paper](http://arxiv.org/abs/1512.03547) on arXiv for his quasipolynomial-time algorithm for GI.

**Update (2017-01-04)**: Babai [retracted](http://people.cs.uchicago.edu/~laci/update.html) the claim that the algorithm is in quasipolynomial time, according to the new analysis the algorithm is in subexponential time $\exp \exp(\tilde{O}(\sqrt{\lg n}))$ which is inside $2^{n^{o(1)}}$.

**Update (2017-01-09)**: Babai [reinstated](http://people.cs.uchicago.edu/~laci/update.html) the quasipolynomial time claim, replacing the offending procedure with a more efficient one.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-isomorphism
> **Comments:**
> **username_1**: Are there complexity-theoretic conjectures ruling out polynomial time algorithms?  
> **username_0**: I do not know. I guess it is possible that ruling out Quasi-PTIME algorithms would require more "natural" and hence weaker conjectures.  
> **username_2**: I think many people do think it has a polynomial time algorithm, and AFAIK such an algorithm would not have any complexity theoretic consequences.  
> **username_0**: @HuckBennett Is there any justification for this belief?  
> **username_2**: @MohammadAl-Turkistany: Look at Scott's comment #13 here: http://www.scottaaronson.com/blog/?p=690.  
> **username_0**: @HuckBennett A counter argument is that IF is in NP $\cap$ CoNP while GI is not known to be in CoNP.  
> **username_3**: Also, I think there are many people who believe GI does *not* have a poly-time algorithm. For example, in Babai's 1995 survey (Handbook of Combinatorics vol. II) he says "None of the problems mentioned in this section [including GI], with the possible exception of isomorphism of groups given by a Cayley table, is expected to have polynomial time solution."  
> **username_3**: @MohammadAl-Turkistany: Why do you guess that ruling out quasi-poly algorithms would require "more 'natural' and hence weaker conjectures"? It seems that by definition ruling out quasi-poly algorithms requires a *stronger* conjecture than ruling out poly-time algorithms. As for naturality, I have no feeling either way for one lending itself to more "naturality" than the other; do you have some intuition for this?  
> **username_0**: My intuition is that we have natural problems such as dominating set in tournaments which has trivial and natural quasi-polynomial time algorithm. So, I thought ruling out quasi-polynomial time algorithms for GI would require some natural conjecture that uses a natural characterization of quasi-polynomial time algorithms. So, all depends on what natural means.  :)  
> **username_0**: @HuckBennett Another argument, we do have efficient quantum algorithm for IF while we are not able to find any polynomial time quantum algorithm for GI.  
> **username_3**: This isn't quite what you're asking for, but it's the best I know of: Group Isomorphism has a natural and easy quasi-polynomial-time algorithm, but there is provably no $\mathsf{AC}^0$ reduction from GI to GroupIso: http://eccc.hpi-web.de/report/2010/117/. A formally easier question than what you ask, but still wide open, is to prove that there is no poly-time reduction from GI to GroupIso.  
> **username_0**: I am aware that GI is not known to be hard for $P$.  
> **username_4**: After two years I believe we have an answer. Laszlo Babai has proved that GI has a quasi polynomial time algorithm. Source: https://lucatrevisan.wordpress.com/2015/11/03/laci-babai-and-graph-isomorphism/  
> **username_5**: related: [GLL post](https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/) about Laszlo Babai's talk next week about GI being in QP.  
> **username_5**: http://people.cs.uchicago.edu/~laci/quasipoly.html  
> **username_6**: @user3415207 Not an answer to this here question, though.  
> **username_6**: @user3415207 [Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.  
> **username_7**: @Raphael ... and Babai restored his claim (same link as yours).  
> **username_6**: @Danny Exciting times!  

---

## 3 answers

### Answer by username_3 on 2017-01-10. Score: 6

As far as I can tell, if you ask simply about the consequences of the mere fact (as a black box) that GI is in QP, I think the answer is very little. The one thing I can think of, which is not a theorem but a consequence for research directions, is to *Group* Isomorphism. Since GroupIso reduces to GI and we don't even know if GroupIso is in P, putting GroupIso into P can be seen as an important obstacle to putting GI into P (if you think the latter might be the case).

However, since the trivial algorithm for GroupIso is $n^{\log n + O(1)}$, back when the complexity of GI was up at $2^{\tilde O(\sqrt{n})}$, we had a long way to go in improving the complexity of GI before GroupIso became an *immediately relevant* obstacle to putting GI into P. But if GI is in QP, then GroupIso becomes a much more relevant obstacle to further improvements in GI. (Of course, the exponent of the exponent in the quasi-polynomial is still a potentially relevant gap, but the gap becomes a *lot* smaller when GI is in QP.)

> **Comments:**
> **username_0**: It appears that we are not able to improve on much weaker upper bound of testing the isomorphism of projective planes ($n^{O(\log \log n)}$) . See http://cstheory.stackexchange.com/questions/34773/testing-isomorphism-of-projective-planes  
> **username_3**: @MohammadAl-Turkistany: Yes, but then my same argument applies: if GI is "way" up at quasipoly, then ProjPlaneIso is very far from being an obstacle to putting GI into P. Once GI is in time $n^{O(\log \log n)^c}$ for some $c$, then ProjPlaneIso would become a relevant obstacle. So, at the moment, it would seem that GroupIso is the more immediate obstacle - maybe someday ProjPlaneIso will be...  
> **username_8**: @JoshuaGrochow Would you agree with me that the approach taken by François Le Gall and David J. Rosenbaum in [On the Group and Color Isomorphism Problems](https://arxiv.org/abs/1609.08253) makes sense? Or at least that they do treat some questions that could come up after gaining a basic understanding of László Babai’s result?  
> **username_3**: @ThomasKlimpel: I agree that their paper makes sense, though I don't yet see how to take advantage of their insights (despite understanding most of Babai's proof).  
> **username_0**: Don't you believe that GI in QP would ultimately lead to placing GI in limited nondeterminism class such as $\beta_k P $?  

---

### Answer by username_9 on 2017-01-30. Score: 3

Concerning the last question: the time hierarchy theorem immediately implies that QP has no complete problems under polynomial-time many-one or Turing reductions. (On the other hand, every problem save $\varnothing$ and $\Sigma^\*$ is QP-hard under *quasi-polynomial* reductions.) Thus, assuming Babai’s result is correct, GI is *not* QP-hard.


---

### Answer by username_8 on 2017-01-06. Score: 0

> What would be the complexity theoretic consequences of a quasi-polynomial time algorithm for the Graph Isomorphism problem?

More or less similar to the consequences of the deterministic polynomial time algorithm for primality testing, the deterministic polynomial time algorithm for linear programming, and the other case where practically efficient (randomised) algorithms (with rare pathological examples where the algorithm became inefficient) were know and in use for a long time. It confirms the conjecture that practical efficiency is a good indicator for the existence of deterministic theoretical algorithms overcoming the issues of the rare pathological examples.

> Would a quasi-polynomial time algorithm for GI refute any famous conjectures in complexity theory?

No, the conjectures rather go to the opposite site, namely that GI is in P. Since GI is in NP, it won't be possilbe to refute this type of conjecture anytime soon.

> Can we efficiently reduce Minimum Dominating Set in Tournaments problem to GI?

Minimum Dominating Set is not an isomorphism problem, hence there is no reason why it should be expected to be reducible to GI.

> Is there any conjecture ruling out GI being hard for QP?

We don't even know how to reduce the string isomorphism problem to GI, and this is at least an isomorphism problem. Babai's proof showed that string isomorphism was in QP, so ... And what is being hard for QP even supposed to mean? Hard under polynomial time reductions?

---

From the introduction of [On the Group and Color Isomorphism Problems](https://arxiv.org/abs/1609.08253) by François Le Gall and David J. Rosenbaum

> The complexity of isomorphism testing problems is worthy of study both because they are fundamental computational questions and also because many of them are not known to be in P, but nevertheless appear to be easier than the NP-complete problems. The most heavily studied of these is the graph isomorphism problem.

I believed I knew that all isomorphism testing problems of finite structures can be reduced to the graph isomorphism problem. Hence I believed that graph isomorphism was the "correct general" isomorphism problem to rule them all. The string isomorphism problem used in Babai's paper revealed that my belief was not fully justified, since it is still unknown whether the string isomorphism problem can be reduced to the graph isomorphism problem. Hence the generalized graph isomorphism problem $\mathsf{GI}^\*$ and the generalized group isomorphism problem $\mathsf{GrI}^\*$ are defined (in the above paper, but the authors rightly wonder why nobody did it before), which add the missing pieces from the string isomorphism problem. (And color isomorphism problem is just a different name for the string isomorphism problem. The name color automorphism problem goes back to the initial papers of Babai and Luks, the name string isomorphism occurs later in their paper on canonical labeling.)

Since Babai's algorithm was a quasi-polynomial time algorithm for the string isomorphism problem (i.e. for $\mathsf{GI}^\*$), the consequence was that isomorphism testing for most types of finite structures should be expected to be quite doable. One application of such isomorphism testing is to list all different types of non-isomorphic structures with certain properties within a given range. Well, actually that application works much better with algorithms for canonisation (as opposed to mere isomorphism testing of two given structures), but the additional slowdown wouldn't change the *principal* polynomial or quasi-polynomial time bound for those problems.

---

**Edit:** This answer was given in the context of the retraction of Babai's result, before he announced a fix. It suggests that the slight generalization of the graph isomorphism problem suggested by the string isomorphism problem is the really important problem. The implicit expectation here is that any *reasonable* algorithm for the graph isomorphism problem will lead to a similar algorithm for the generalized graph isomorphism problem. The generalized problem is polynomial time equivalent to the [set-stabilizer problem](https://groupprops.subwiki.org/wiki/Set-stabilizer_problem), the [group intersection problem](https://groupprops.subwiki.org/wiki/Group_intersection_problem), the coset intersection problem, the [set transporter problem](https://groupprops.subwiki.org/wiki/Set_transporter_problem), ... The idea behind this expectation is that the generalized problem will occur in the *recursive part* of any reasonable algorithm, so it has to be addressed anyway. (And it is quite possible the the generalized problem is polynomial time equivalent to graph isomorphism.)

Now Joshua Grochow's comments indicates that I wasn't successful in explaining the conceptual importance of the missing pieces from the string isomorphism problem. For infinite structures, it may be easier to appreciate that a valid isomorphism should not just preserve the given structure, but also belong to an appropriate category of functions (for example the category of continuous functions). For finite structures, the analogous phenomenon mostly occurs for quotient structures, where the appropriate category of functions should be compatible with the given quotients. The Johnson stuff is a typical example of such quotients, for example partition logic is working over the two element subsets of some base set. Also note that restricting the allowed category for the isomorphisms often makes the isomorphism testing problem easier, and that this might be the really crucial point for the importance of the generalized problem.

The problem with generalizations of the graph isomorphism problem is where to stop. Why not generalize so far as to encompass the permutation group isomorphism problem? This question is really hard, since many non-trivial results for graph isomorphism will probably carry over to permutation group isomorphism as well. But here it feels more reasonable to treat computational permutation group theory as a subject in its own right, even if it has indeed close connection to the graph isomorphism problem.

> **Comments:**
> **username_3**: First, as far as I understand it, string iso = color iso; what "artificial restrictions" do you mean? Second, the well-known result about isomorphism of all finite structures reducing to GI is a statement about finite structures definable in first-order logic. String isomorphism/color isomorphism doesn't fall into that class, since it asks not just whether two strings are isomorphic as first-order structures, but whether there is a first-order isomorphism between two strings where the isomorphism lies *in a given subgroup of $S_n$*.  
> **username_8**: @JoshuaGrochow For color iso, the colors are just arbitrary numbers (wlog restricted to [n]). For string iso, the strings are given over a fixed finite alphabet. I thought it was a binary alphabet, but I misremembered this. I just remembered that I was initially confused whether color iso was just a different name for string iso. So when I decided to read that paper after Laszlo retracted his claim, it felt like a difference to me. Maybe it really is a difference, because "over a finite alphabet" communicates "fix your favorite finite alphabet, it won't make any difference". Which is true.  
> **username_3**: Even if they are making this distinction, the two problems you state are equivalent: over a fixed finite alphabet, simply use substrings of length $\log n$ to encode colors from $[n]$, and then change your group so that it only ever moves these substrings as a whole.  
> **username_8**: @JoshuaGrochow This is exactly what I meant by *it won't make any difference". Which is true.* I now tried to address your "String isomorphism/color isomorphism doesn't fall into that class" comment. I enjoyed learning some lessons from Andreas Blass and Yuri Gurevich on the way, who also try to focus on conceptual points. I am happy that Babai fixed his algorithm now, so that I feel no obligation (or pressure) to investigate whether graph isomorphism and string isomorphism are polynomial time equivalent. (Which was the context why I wrote that answer.)  
> **username_10**: I am confused why you compare progress on GI with derandomization results.  
> **username_8**: @SashoNikolov Because nobody plans to replace the existing practically efficient algorithms with the new theoretically efficient algorithm. The entire first part of this answer is just meant to spell out the obvious.  

---

