Please create an account to participate in the Slashdot moderation system

typodupeerror

## Breakthrough Algorithm Reported For Graph Isomorphsim (scottaaronson.com) 86

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.
This discussion has been archived. No new comments can be posted.

## Breakthrough Algorithm Reported For Graph Isomorphsim

• #### Interesting (Score:3)

on Friday November 06, 2015 @02:28PM (#50878729)
Back when I was doing my Master's Project I used the tool NAUTY [stonybrook.edu] extensively to test out isomorphism on graphs I was interested in. Checking around a little bit it looks like NAUTY does a fairly good job in most cases, but there are a few classes of graphs which gives it fits. Something that this new algorithm addresses.
• #### Re: (Score:1)

by Anonymous Coward

Actually, probably not. This algorithm's worst case is still going to take a long time, just slightly less bad than Nauty's worst case. I'll be surprised if this leads to any practical benefits (but I am also going to jump straight on the theory to find out if it will!)

• #### It's been a while (Score:4, Interesting)

on Friday November 06, 2015 @02:31PM (#50878757) Homepage

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?

• #### Re:It's been a while (Score:5, Informative)

on Friday November 06, 2015 @02:44PM (#50878849)

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

• #### Re: (Score:1)

by Anonymous Coward

Subgraph isomorphism trivially encodes k-Clique and Hamiltonian Path, so you're most certainly correct.

• #### Re: It's been a while (Score:4, Informative)

by Anonymous Coward on Friday November 06, 2015 @02:45PM (#50878859)

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

• #### Re: (Score:1)

by Anonymous Coward

Knuth put it pretty well (though I don't recall the exact verbiage) when he said something along the lines of "P=NP but the solution is going to be virtually useless outside of the one problem it solves." On a philosophical note if you proved P=NP you would essentially have God-like creative power, knowing in an instant how to do anything (does this ball float? "no, it's not floating" would be as easy to tell as "how do I make it float?".) But while P=NP, the solution is so context-specific the current st

• #### Re: (Score:2)

Knuth put it pretty well (though I don't recall the exact verbiage) when he said something along the lines of "P=NP but the solution is going to be virtually useless outside of the one problem it solves." On a philosophical note if you proved P=NP you would essentially have God-like creative power, knowing in an instant how to do anything ...

Absolutely not.

What Knuth argues is that he thinks P=NP, but any proof to that effect will be a non-constructive proof (aka "existence proof"), i.e. merely a proof that such a fact is true. It would not solve any problem in that case. And is would most especially not give you any "God-like powers". This sort of thing is common in mathematics - you can prove a thing exists, but that proof provides no clue how to actually find an example of the that thing.

• #### Re: (Score:2)

The "God-like creative power" comes from simplifying "P=NP" as "it's as easy to recognize a correct answer as it is to come up with one". I've seen people then go from this simplification to "proving" that P!=NP because "it's harder to write a song than to listen to it". It's nonsense for a lot of reasons. The most striking is the assumption that for every single mental task that humans attempt, we always use the absolute most efficient algorithm in all of existence. Reversing that to say that "proving
• #### Direct applications (Score:2)

Any examples of direct/proximate applications to layperson problems?

• #### Re: (Score:3)

There are a lot of natural problems that involve graph theoretic aspects or graph isomorphism in particular. Chip design is one major example, where it is used in establishing that different designs for part of a chip really will do the same thing. However, it is not that likely this will end up having a substantial practical implication by itself because for most purposes graph isomorphism is an easy problem. In particular, for two random graphs it is easy to tell whether they are isomorphic or not (and fo
• #### Re: (Score:1)

No. Expect this to maybe have an impact during the next 100 years or so. Mathematicians are not like the stupid masses that want everything to pay off _now_. They see the value in doing things with a very long-term perspective.

• #### Re: (Score:2)

No. Expect this to maybe have an impact during the next 100 years or so. Mathematicians are not like the stupid masses that want everything to pay off _now_. They see the value in doing things with a very long-term perspective.

Well, there are three possible outcomes.

1) Absolutely nothing comes of it. Happens, but when you're doing pure research you don't know.

2) Potential uses 5 years down the road or longer. We don't know why we might need it now, but the research is out there, and maybe someone down the l

• #### Re: (Score:2)

We used GI algorithms back in the 80's in checkers for had-routed cell-based IC's - we checked see if the connection graph of the routed chip matched the netlist of the circuit. It did find errors, but was very slow back then.

• #### Re: (Score:2)

It is generally thought that the group isomorphism problem is easier than the graph isomorphism problem. If that is the case (and I don't recall whether it is proven or just believed), then based on this result, group isomorphisms are probably in P. This would seem to be a problem for cryptographic applications that rely on the discrete log problem such as Diffie Hellman and elliptic curve, but I would love to hear from someone working in cryptography to explain why that would not be the case.

• #### Re: (Score:2)

The groups in cryptography are very large, and it is not clear how finding an isomorphism to another (equally large group) would help calculate logs faster.

• #### Re: (Score:2)

We don't actually have a proof that group isomorphism is in P, and we don't also know whether this new work will help at all with that problem. One might hope that one could take a pair of groups, convert them to the relevant graphs and then run this, but that's unlikely to be helpful since we already have group isomorphism algorithms that work in quasipolynomial time- in fact the most obvious non-trivial one does so. Note also that in the case of the groups arising from Diffie-Hellman and similar procedure
• #### Typo: ... determining when graphs are isomorphic. (Score:3, Interesting)

by Anonymous Coward on Friday November 06, 2015 @03:10PM (#50879041)

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

• #### Re: (Score:2)

Yes, and in the title isomorphism is spelled wrong also. Not my best submission.
• #### Nice to see technical stuff on /. again (Score:4, Insightful)

on Friday November 06, 2015 @03:13PM (#50879063)

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

• #### Re: (Score:2)

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

Not me. Every week I'm baffled by a Dice story about oppressed female programmers.

• #### P vs. NP is not that important for crypto (Score:3)

on Friday November 06, 2015 @03:14PM (#50879071)

The assumption P!=NP is a shortcut that simplifies things. But if I have, say, some computation that is O(n) with key and Omega(n^3) without the key and scales, then I can still do public-key crypto with it, just slower. Now, if it turns out that P=NP (unlikely), some things will need to be changed as a whole class of computations would not be ensured to be exponential anymore, but it does not break things fundamentally. Same if some problems used for public-key crypto turn out to be in P, not NP. The idea is still sound, it just makes things less convenient.

That said, this is cool research!

• #### Laszlo! (Score:2)

Laszlo! The finest mind of his time!
• #### Marks (Score:2)

I thought you could easily identify them by the cool marks on their arms??

• #### Relation to cryptography (Score:1)

Graph isomorphism is not used in any popular encryption scheme, but saying that it has no applications in cryptography is incorrect. See this ZKP scheme [wikipedia.org], obsoleted by the new algorithm.

#### Related LinksTop of the: day, week, month.

"I have not the slightest confidence in 'spiritual manifestations.'" -- Robert G. Ingersoll

Working...