Slashdot Mirror
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.
It's readable, so long as you understand that P and NP are complexity classes used to describe the complexity of problems, rather than the first initial of the person being discussed in the next sentence.
More or less, it's just saying that the problem being discussed is closer to P than NP in terms of its complexity (i.e. we can now prove that it isn't as complex as it was theorized it might be), and that the proof is built on top of other proofs that span hundreds of research papers. That's all.
I believe that Subgraph Isomorphism is NP-Complete, but Graph Isomorphism is not.
No, it's one of the problems in NP that have neither been proven to be in P nor to be NP-conplete.