You're reading: News, Phil. Trans. Aperiodic.

László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time

László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.

And it looks like he’s done it! Babai presented the first part of his work in a seminar at the University of Chicago on the 10th of November. Gabe Gaster, who attended the talk, live-tweeted it. You can relive the excitement with a Storify of the whole thing. Is this the first live-tweeting of a groundbreaking mathematical advance?

Babai has also put the video of his talk on his homepage. It’s 100 minutes long, and if you want to skip to the bit where the audience breaks into the restrained applause that Hollywood will re-enact as a standing ovation ending in Babai being carried out of the building by his peers, it’s at 1:34:45.

So, how did he do it? Lots of finite group theory. Jeremy Kun has written a very good blog post explaining the broad outline of the proof. I’ll nab this theorem statement from Jeremy:

Theorem: There is a deterministic algorithm for GI which runs in time $2^{O(\log^c(n))}$ for some constant $c$.

I won’t pretend I’ve read even Jeremy’s summary in detail (I’ve got a dog and a wife to feed tonight) but I enjoy the term “split-or-Johnson routine” purely because it could easily be a Nicholas brothers dance. László has given one more talk and is scheduled to do another, titled “A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism problem” and “Graph Isomorphism in Quasipolynomial Time II: The ‘Split-or-Johnson routine'”. I don’t think anyone has live-tweeted those though, so we’ll have to wait until the full solution appears in writing to find out all the nitty-gritty.

We also have to wait to find out if Babai is even right – as his homepage says, none of this has been peer-reviewed yet! But for now, we’ve got a lot of new ideas that definitely represent a big breakthrough.

babaitalks

6 Responses to “László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time”

  1. Avatar Brian Hayes

    “… graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.”

    Please don’t overexcite my excite-o-meter. Graph isomorphism is indeed in NP, but it’s not NP-complete. If you want to prove P = NP, you need to find a polynomial-time algorithm for an NP-complete problem (e.g., satisfiability, traveling salesman problem). Showing that graph isomorphism is in P would not change the status of the p = NP question. (But it would be pretty nifty anyway.)

    Reply
    • Avatar James

      A small pedantic remark: You state that graph isomorphism is not NP-complete, but if we had proof of that then that implies P != NP. It is in fact not known whether graph isomorphism is NP-complete or not.

      But apart from that, I agree with you, and came down to the comments to object to that sentence as well.

      Reply
    • Avatar El-Andalussi

      Brian Hayes wrote:
      “… Graph isomorphism is indeed in NP, but it’s not NP-complete. …”
      it’s not NP-Complet or it’s not KNOWN to be NP-Complet?

      Reply

(will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>