40
$\begingroup$

The Graph Isomorphism problem (GI) is arguably the best known candidate for an NP-intermediate 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 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) 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 on arXiv for his quasipolynomial-time algorithm for GI.

Update (2017-01-04): Babai retracted 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 the quasipolynomial time claim, replacing the offending procedure with a more efficient one.

$\endgroup$
  • 6
    $\begingroup$ I think many people do think it has a polynomial time algorithm, and AFAIK such an algorithm would not have any complexity theoretic consequences. $\endgroup$ – Huck Bennett Nov 25 '13 at 15:08
  • 7
    $\begingroup$ 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: 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. $\endgroup$ – Joshua Grochow Nov 26 '13 at 15:32
  • 14
    $\begingroup$ After two years I believe we have an answer. Laszlo Babai has proved that GI has a quasi polynomial time algorithm. Source: lucatrevisan.wordpress.com/2015/11/03/… $\endgroup$ – user3415207 Nov 4 '15 at 6:39
  • 8
    $\begingroup$ @user3415207 Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$ – Raphael Jan 4 '17 at 21:46
  • 6
    $\begingroup$ @Raphael ... and Babai restored his claim (same link as yours). $\endgroup$ – Danny Jan 11 '17 at 15:11
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 cstheory.stackexchange.com/questions/34773/… $\endgroup$ – Mohammad Al-Turkistany Jan 10 '17 at 21:43
  • $\begingroup$ @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... $\endgroup$ – Joshua Grochow Jan 10 '17 at 22:21
  • $\begingroup$ @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 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? $\endgroup$ – Thomas Klimpel Jan 10 '17 at 23:33
  • $\begingroup$ @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). $\endgroup$ – Joshua Grochow Jan 11 '17 at 6:31
  • $\begingroup$ Don't you believe that GI in QP would ultimately lead to placing GI in limited nondeterminism class such as $\beta_k P $? $\endgroup$ – Mohammad Al-Turkistany Jan 16 '17 at 10:00
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 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, the group intersection problem, the coset intersection problem, the 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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Joshua Grochow Jan 11 '17 at 6:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Thomas Klimpel Jan 11 '17 at 8:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Jan 14 '17 at 16:01
  • 1
    $\begingroup$ @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.) $\endgroup$ – Thomas Klimpel Jan 30 '17 at 10:23
  • $\begingroup$ I am confused why you compare progress on GI with derandomization results. $\endgroup$ – Sasho Nikolov Jan 30 '17 at 10:25

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.