66
$\begingroup$

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this week, and the abstracts are here. I'm not an expert in this field (for instance, I had to look up what polylog means), but clearly this is a very significant result. Babai is a giant in this field, so let's assume for now that the claimed result is correct.

(1) What are some implications of this result in complexity theory?

For example: This problem is NP, but is not known to be NP-complete. If it were NP complete, and if the algorithm were polynomial time, then we'd know P = NP and that would be huge. Does this new result give us any insight into the class of problems that are NP but not known to be NP complete? Does it prove that Graph Isomorphism is not in some other class of problems (e.g. does anyone study the class of exponential but not quasi-polynomial time problems)?

(2) Are there other important problems that reduce to the graph isomorphism problem that are now known to be solvable in quasi-polynomial?

Babai's abstract mentions the Coset Intersection problem and the String Intersection problem. I can guess what those are from the name. Are there other well-studied problems that reduce to graph isomorphism?

(3) How far is quasi-polynomial from polynomial?

Based on the linked thread above, polylog generally means $O(\log(n)^k)$ in complexity theory. If so, then exp[\log(n)^k]) = exp[k]*n, which doesn't look all that much like polynomial time, unless you can bound $k$ by a constant that doesn't depend on $n$. But perhaps I'm misunderstanding the whole story, in which case I'd love to be set straight. What would be the next step to getting the bound lower, from the perspective of complexity theory?

Obviously, the proof hasn't appeared in print yet, so I'm not asking if the proof can somehow be made polynomial instead of quasi-polynomial, and I'm definitely not asking if it's correct. I'm asking what it implies if it's correct, and how much it changes the current playing field for complexity theory.

EDIT (based on the comments):

(4) Is there any known implication of this new result in Quantum Computing?

Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ I think you have the wrong picture of exp((log n)^k): It looks to me like n^{f(n,k)} where f(n,k) is a (perhaps slowly) growing and unbounded function of its arguments. Until a lower bound on the runtime is established ( or an NP-complete problem is reduced to GI ), I don't think it will have much immediate impact on our knowledge of the polynomial hierarchy. Nonetheless, it is quite a worthy achievement: even if a flaw is found, I think the material Babai generated will be worthy of a generation or more of study. Gerhard "Hopes There Is No Flaw" Paseman, 2015.11.12 $\endgroup$
    – Gerhard Paseman
    Commented Nov 12, 2015 at 17:40
  • 1
    $\begingroup$ I assume this should be community wiki. That said, there is a nice entry in Trevisan's blog about this: lucatrevisan.wordpress.com/2015/11/03/… $\endgroup$
    – Delio Mugnolo
    Commented Nov 12, 2015 at 20:05
  • 10
    $\begingroup$ Polylog is indeed a wonderful abbreviation: it takes more space to write than $\log^k n$ and obscures meaning. $\endgroup$
    – Christian Remling
    Commented Nov 12, 2015 at 21:39
  • 10
    $\begingroup$ @ChristianRemling Had you written $(\log n)^k$, I would have agreed with you. But $\log^k n$ could just as easily mean $\log (\log (\dots \log n)))$, a function that grows extremely slowly. My understanding is that functions this slow do not appear in computer science but do sometimes appear in, say, analytic number theory. $\endgroup$
    – Theo Johnson-Freyd
    Commented Nov 13, 2015 at 5:15
  • 4
    $\begingroup$ @TheoJohnson-Freyd That grows extremely quickly compared with the inverse Ackermann function, which is the optimal amortized time complexity for the union-find problem in computer science: en.wikipedia.org/wiki/Disjoint-set_data_structure $\endgroup$
    – Adam P. Goucher
    Commented Nov 13, 2015 at 11:34

4 Answers 4

Reset to default
43
$\begingroup$

The short answer is that there are no implications.

As Scott Aaronson said on his blog, the fact that even a polynomial time algorithm for GI has no implications for complexity classes is one reason some people conjectured that GI might be in P. He continued:

In fact, the main implication for complexity theory, is that we’d have to stop using GI as our flagship example of a problem that has statistical zero-knowledge proof protocols and dozens of other amazing properties, despite not being known to be in P, which would make all those properties trivial. :-) It’s similar to how the main implication of PRIMES in P, was that we had to stop using primality as our flagship example of a problem that was known to be in randomized polynomial time but not deterministic polynomial time. Still, I managed to adapt in my undergrad class, by talking about the randomized test for primality, and then treating the fact that it’s actually in P as just a further amazing wrinkle in the story. And I’d be happy to adapt similarly in the case of GI…

Similarly there are no implications for quantum computing.

As for the prospects for further improvement, the best reference as of this writing may be Jeremy Kun's notes on Babai's talk. One key point is that Babai's algorithm relies on a strategy that he calls "split or Johnson" and he can show that this strategy is not enough to put GI in P.

UPDATE: Babai has posted a preprint to the ArXiv.

UPDATE: Babai's talk at the Institute for Advanced Study is available online. IMO this talk is much better than the very first talk he gave at Chicago; he's had time to prepare slides and greatly clarify the presentation.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Perhaps for quantum computing there is a chance to relate the new algorithm to the hidden subgroup problem for the symmetric group, though? $\endgroup$
    – Sam Hopkins
    Commented Nov 13, 2015 at 14:51
  • 2
    $\begingroup$ @SamHopkins : There's nothing in the recent advance to suggest that we're any closer to solving the hidden subgroup problem for the symmetric group. $\endgroup$
    – Timothy Chow
    Commented Nov 13, 2015 at 21:16
  • 2
    $\begingroup$ It's worth noting that given the above answer, people might wonder why this is a big deal than. The answer is that Graph Isomorphism has become a big deal because no one made progress on it for 30 years. This is a good example of a problem that's famous because it's hard, not because it's deep. $\endgroup$
    – Stella Biderman
    Commented Nov 14, 2015 at 17:05
  • 7
    $\begingroup$ Graph Isomorphism may not be deep, but it is wide. Just in my narrow experience, I have come across problems in industry as well as in research in which having a good and fast algorithm for GI would help substantially. If Babai has clearly revealed the hard parts, some industry code may be adapted to check for these hard parts before running. Gerhard "Circuit Layouts And Algebraic Structures" Paseman, 2015.11.15 $\endgroup$
    – Gerhard Paseman
    Commented Nov 16, 2015 at 0:36
  • 2
    $\begingroup$ @StellaBiderman: I suppose it may not seem particularly deep in the sense of having impact on many other seemingly unrelated problems. But from a different standpoint, I think it is a deep, fundamental question, whose techniques rely on and have inspired decades worth of research into the theory of permutation groups... $\endgroup$
    – Joshua Grochow
    Commented Mar 15, 2016 at 18:10
15
$\begingroup$

An update from Babai:

http://people.cs.uchicago.edu/~laci/update.html

The main result, which appears to have been vetted at this point with extreme care, has weakened somewhat. His bound is now $\exp(n^{o(1)})$, a big improvement over the previous $\exp(n^{1/2 + o(1)})$, but no longer quasi-polynomial.

UPDATE: Babai is now claiming a new Split-or-Johnson subroutine restores the quasipolynomial claim! http://people.cs.uchicago.edu/~laci/update.html

Improve this answer
$\endgroup$
2
10
$\begingroup$

(a) What is the computational complexity of GI, is an example of a major question that we genuinely did not know the answer to even on a heuristic or conjectural level. Even now, whether GI is in P is everybody's guess. Of course, the new result gives some support for the possibility that GI is in P and the methods may be relevant for attacking it.

(b) We don't know even if GI belongs to coNP and proving this will also be a major breakthrough. Again, the new result gives some support to GI being in coNP. Here, it is (I think) a clear computational-theoretic expectation, given the derandomization view on randomness in complexity, that GI is in coNP, but, even so, it is much beyond any derandomization that can be proved. Again, the methods of the new proof may be relevant.

(c) The quasipolynomial algorithm for GI is, by itself, an off-scale scientific achievement. One important application would be to support the wide (while not universal) claim that "If it is easy in practice theory will follow." An earlier example of this was the fact (proved in 1979) that LP is in P. (Another insight from LP yet to be tested in this case is that "If it is easy in theory, practical fruits will follow".)

(d) There are various computational questions about permutation groups, groups, and group representation that the new breakthrough may be relevant to. It can certainly lead to much activity, interest and progress in computational questions for groups.

(e) That that hidden subgroup problem is so much more general/difficult than GI is a clear insight of the new result. There were some earlier indications for that but it was far from being clear, even on a conjectural/heuristic level.

Improve this answer
$\endgroup$
7
$\begingroup$

EDIT: The paper is now available on arxiv

Video from the first talk can be found here: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4

This should shed light on implications for other hard problems, e.g. the Coset Intersection problem and the String Intersection problem, as well as the quasi-polynomial nature of the solution. Thanks, Tim Chow, for the link to Scott Aaronson's blog. It's really a treasure trove. For example, in Comment #9 he gives a great answer for (3) above. It says there are problems where we have "good evidence that quasipolynomial time is the best possible...Three examples are calculating the VC dimension of a set, finding an approximate Nash equilibrium of a two-player game, and approximating the value of a free game." So it seems quasipolynomial is still quite far from polynomial and really Babai is adding GI to a list of problems such as these three examples.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The description of the string isomorphism problem on Scott Aaronson's blog reminds me of the word problem. I wonder if there might be an application of Babai's ideas to finding faster solutions to the word problem for groups where it's solvable, or increasing the class of groups on which it's solvable. I suppose we won't know till we see Babai's preprint. $\endgroup$
    – David White
    Commented Nov 17, 2015 at 16:07
  • 3
    $\begingroup$ In comment #110 at Scott's blog, Greg Kuperberg mentions the Uknottedness problem and says "The news this month over graph isomorphism suggests that one day we might see a fast algorithm for determining whether a knot diagram represents the unknot." This is not an answer to (2) as much as the three examples above, but is close. $\endgroup$
    – David White
    Commented Nov 17, 2015 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .