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.
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.
P is not his first name:D
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion. -- Spazmania (174582)
Back when I was doing my Master's Project I used the tool NAUTY 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.
Happy people make bad consumers.
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.
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.
Any examples of direct/proximate applications to layperson problems?
Please check your calendar. Today is not Troll Tuesday.
"Transparent" is a shit show that trades on every stereotype going. A man in drag is NOT a transsexual.
http://www.lmgtfy.com/?q=isomo...
If it weren't for deadlines, nothing would be late.
you clearly are not familiar with Troll Goodness Its Friday.
also i thought it rated more funny than anything else :)
(The last sentence wrongly writes "groups" instead of "graphs".)
It's been a while since I've seen a story I didn't understand on this site. Keep up the good work!
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!
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
Laszlo! The finest mind of his time!
No, you're thinking of xenomorphs. Isomorphs are the miracle AI folks hunted by C.L.U. 2.0.
Is that why you have one space after your sentences? Never mind the double space has been effectively pushed out of grammatical styles.
I thought you could easily identify them by the cool marks on their arms??
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 number of other topics that we discuss here, I have little or no working knowledge, so I'm happy to have others share information and links to things I don't know, and I assume the same of others.
It was not my intention to insult you, nor was it my intention to stroke my own ego. It was simply my intention to point you towards further reading if you were interested in pursuing it. Feel free to ignore it. Feel free to insult me, if you want. But might I suggest that you give people the benefit of the doubt around here in the future? Most of the folks are decent ones.
Yes, and in the title isomorphism is spelled wrong also. Not my best submission.
How can something be closer to P than to NP? P is a subset of NP.
You mean NP-complete, right?
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
I stubbornly still use double spaces after sentences.
"Evil will always triumph over good, because good is dumb." - Dark Helmet (Spaceballs)
I do it out of spite sometimes when writing a paper. I got dinged for it so much in school.
Spacing around punctuation has been steadily declining as time goes on. 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. Double spacing originated as a typewriter-user's emulation of this practice, and as literacy and equipment improved, convention came to cater to both minimalism (thereby also saving paper) and skilled readers.
Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
/. 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.
We hope your rules and wisdom choke you / Now we are one in everlasting peace
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 like r, v, and w) rather than driven by pure physical limitations.
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 aware that I know absolutely nothing where the domain is concerned and the article is sorely lacking in enough information for me to give a qualified opinion. I'd question why genetics would be using limited data sets instead of looking at the whole and then reducing from there but, again, this is not something I'm fluent in. I'll also include the caveat, I did not work in any area where this would have been a concern - as far as I can tell.
I'm a little disappointed that I had to skim the article. I feel dirty for it. It is, after all, Friday.
"So long and thanks for all the fish."
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.
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
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.
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, obsoleted by the new algorithm.
Yes, there were national fads that came and went—and the practice wasn't always universal, albeit beneficial for legibility to an inexperienced reader and safer for the type. By making the spaces not a fixed part of the block, it was still possible to remove them for tighter typesetting in limited spaces and to make sure there weren't unnecessary gaps at the ends of lines. Here's an example from 1808 that puts spaces around colons and semicolons, but not apostrophes, periods, or commas—and quotation marks are handled irregularly (they're hard to find, but there's an example on page 132, at the bottom.) For a comparable debate, German can be typeset with four different quote patterns (normal English-style quotation marks, using double low-nine inverted quotation marks, guillemets, and inverted guillemets, which is the style used in Switzerland.)
Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
It's not just /. HTML compresses consecutive spaces when rendering unless you explicitly use non-breaking spaces.
*WOOSH*
Person comments on lack of double spaces in HTML formatted text. Proceeds to lack double spaces in his HTML formatted text.
Did you reply to the wrong person?
No; I'm afraid I'm just that boring.
Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
It wasn't that it was boring. It just seemed out of place given my preceding comment.
My thinking was that you might like to be able to place your habits in an historical context, what with the spite and all.
Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!