Slashdot Mirror

← Back to Stories (view on slashdot.org)

Breakthrough Algorithm Reported For Graph Isomorphsim (scottaaronson.com)

Posted by Soulskill on from the math-is-hard dept.

JoshuaZ writes: A major open problem in graph theory is how efficiently one can tell, given two graphs, whether or not they are isomorphic — that is, whether they're the same graph with just the labels changed. This problem is famous, along with factoring integers, as a problem that is potentially in between P and NP in difficulty. Now, Laszlo Babai has reported that he has a quasipolynomial time algorithm which he sketched out at a set of talks at the University of Chicago. Scott Aaronson was one of the first to break the news, and his latest blog entry and its comments contain further discussion of the result. The new algorithm places the problem of graph isomorphism as, at most, just barely above P. Babai's result depends on the classification of finite simple groups, a deep result in algebra whose proof consists of thousands of pages over hundreds of distinct papers. Unlike the problem of factoring integers, improvements in this algorithm are unlikely to impact cryptography in any direct way, since no cryptographic systems depend on the difficulty of determining when groups are isomorphic.

6 of 86 comments (clear)

  1. Re:An unreadable sentence by behrooz0az · · Score: 4, Funny
    Because it's not one sentence:

    The new algorithm places the problem of graph isomorphism as, at most, just barely above P.

    P is not his first name:D

    Babai's result depends on the classification of finite simple groups, a deep result in algebra whose proof consists of thousands of pages over hundreds of distinct papers

    --
    Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion. -- Spazmania (174582)
  2. It's been a while by kamapuaa · · Score: 3, Interesting

    It's been a long while since I studied Computer Science in college, but isn't graph isomorphism a class of NP-Complete? And wouldn't "solving" any one of them open up a huge range of other NP problems, including cyptographic systems?

    --
    Slashdot: providing anti-social weirdos a soapbox, since 1997.
    1. Re:It's been a while by nrjyzerbuny · · Score: 5, Informative

      I believe that Subgraph Isomorphism is NP-Complete, but Graph Isomorphism is not.

    2. Re: It's been a while by Anonymous Coward · · Score: 4, Informative

      No, it's one of the problems in NP that have neither been proven to be in P nor to be NP-conplete.

  3. Typo: ... determining when graphs are isomorphic. by Anonymous Coward · · Score: 3, Interesting

    (The last sentence wrongly writes "groups" instead of "graphs".)

  4. Nice to see technical stuff on /. again by mveloso · · Score: 3, Insightful

    It's been a while since I've seen a story I didn't understand on this site. Keep up the good work!