Breakthrough Algorithm Reported For Graph Isomorphsim (scottaaronson.com)

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.

Comments

It's been a while

[kamapuaa]

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?

Typo: ... determining when graphs are isomorphic.

[Anonymous Coward]

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