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.
Re: An unreadable sentence (Score:2)
P is the name of a complexity class, not Laci Babai's first initial (which is L, coincidentally another famous complexity class). It's two distinct sentences.
Re:An unreadable sentence (Score:5, Funny)
P is not his first name:D
Re: (Score:3, Informative)
It's readable, so long as you understand that P [wikipedia.org] and NP [wikipedia.org] are complexity classes [wikipedia.org] 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.
Re: An unreadable sentence (Score:2)
just admit your mistake and move on. Nobody thought you were stupid until you went after somebody who was trying to help you. Beware the ego.
Re: (Score:2)
Is that why you have one space after your sentences? Never mind the double space has been effectively pushed out of grammatical styles.
Re: (Score:2)
I stubbornly still use double spaces after sentences.
Re: (Score:2)
I do it out of spite sometimes when writing a paper. I got dinged for it so much in school.
Re: An unreadable sentence (Score:3)
Re: (Score:2)
Books from 200 years ago might go so far as to put spaces around commas and semicolons on both sides, with the following space also being larger—a convention also used for periods at the time. This is related to the practice of putting quotation marks and parentheses on the outside; slender punctuation blocks of metal type like periods, commas, and semicolons were fragile, so surrounding them in sturdier blocks made them less likely to get broken when the word was added to the page's master negative (the frame) or if the text needed to be reflowed.
I'm curious why that would be. If additional space was always used in the movable type era, why wouldn't they simply make the block wider? I've seen several 16th century typeset works and at least the ones I've seen had reasonably tight spacing on periods.
I suspect that apparent extra spacing on periods, commas, and semicolons is more due to typographic emulation of french punctuation spacing style and justification aesthetics and potentially some block kerning limitations (e.g., punctuation after letters
Re: (Score:2)
Re: (Score:2)
Did you reply to the wrong person?
Re: (Score:2)
Re: (Score:2)
It wasn't that it was boring. It just seemed out of place given my preceding comment.
Re: (Score:2)
Re: (Score:2)
/. filters out extra spaces between sentences, so he may have typed his post with double spaces. That said double spaces is a dated practice which is not encouraged.
Re: (Score:2)
It's not just /. HTML compresses consecutive spaces when rendering unless you explicitly use non-breaking spaces.
Re: (Score:2)
*WOOSH*
Person comments on lack of double spaces in HTML formatted text. Proceeds to lack double spaces in his HTML formatted text.
Re: (Score:3)
I hope your ego feels better after you added this redundant post showing off your knowledge of undergraduate level complexity theory.
It wasn't redundant at the time I hit "Reply to This", but between getting distracted with work and grabbing the relevant links, I'll admit it was redundant by the time I hit "Submit".
Even so, no, my ego doesn't feel better, because my ego wasn't involved to begin with. I just assumed you were someone who wasn't familiar with complexity classes, which is perfectly fine, since we're not all computer scientists, just like we're not all mechanical engineers, geneticists, or statisticians. When it comes to a nu
Re: (Score:1)
How can something be closer to P than to NP? P is a subset of NP.
You mean NP-complete, right?
Re: (Score:2)
I was just paraphrasing the line from the summary that said:
The new algorithm places the problem of graph isomorphism as, at most, just barely above P
Re: (Score:2)
The complexity classes are bounded by equations (well, they are the upper bounds of families of equations). There is a nice description in the comments on Scott's blog of how there is a gap in those equations (a region with no closed forms) that lies between the polynomial equatuons and the exponential ones. This result would be in the "polynomial greater metropolitan area" as he phrases it.
Re: (Score:1)
I know. But they are all in NP. It makes sense to say "more than polynomial, but less than exponential" but it makes no sense at all to say "closer to P than to NP". I know what they mean, but they're mixing up the terminology.
Re: (Score:2)
I, likely, have the maths covered but lack the domain knowledge - I know little to nothing about genetics nor their alignment or even what that is unless you mean pattern matching of genes to see, for example, ethnicity or some mutation or the likes. If so, then, a quick look (and a lack of specifics in the article) would suggest that it may help in that it would speed up the process and, potentially, reduce false positives - meaning more able to be used deterministically. However, I'd caution one to be awa
Interesting (Score:3)
Re: (Score:1)
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!)
Re: (Score:2)
http://www.lmgtfy.com/?q=isomo... [lmgtfy.com]
Re: (Score:2)
No, you're thinking of xenomorphs. Isomorphs are the miracle AI folks hunted by C.L.U. 2.0.
It's been a while (Score:4, 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?
Re:It's been a while (Score:5, Informative)
I believe that Subgraph Isomorphism is NP-Complete, but Graph Isomorphism is not.
Re: (Score:1)
Subgraph isomorphism trivially encodes k-Clique and Hamiltonian Path, so you're most certainly correct.
Re: (Score:1)
Your ideas intrigue me, and I would like to subscribe to your newsletter.
Re: It's been a while (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.
Re: (Score:1)
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)
Direct applications (Score:2)
Any examples of direct/proximate applications to layperson problems?
Re: (Score:2)
'I already looked at these paths' but this one 'looks different' but is it *really* different.
I distantly recall this sounding similar to determining the actual number of permutations of things -- a ring of beads, Rubik's cube configurations -- as governed by 'group theory'. How much of this graph isomorphism problem falls under group theory?
Re: (Score:3)
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)
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)
Re: (Score:2)
Re: (Score:2)
you clearly are not familiar with Troll Goodness Its Friday.
also i thought it rated more funny than anything else :)
Re: (Score:1)
Ah - but it *is* SJW Friday! It's a bit of a toss-up. I'm not quite sure where it belongs.
Typo: ... determining when graphs are isomorphic. (Score:3, Interesting)
(The last sentence wrongly writes "groups" instead of "graphs".)
Re: (Score:2)
Nice to see technical stuff on /. again (Score:4, Insightful)
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)
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)
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.