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.
(The last sentence wrongly writes "groups" instead of "graphs".)
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 for many practical applications NAUTY will work fine http://www3.cs.stonybrook.edu/... ). This is in contrast to factoring integers where factoring a random positive integer seems very tough. This is also why crypto uses factoring but not graph isomorphism: making a crypto scheme where random instances are easy isn't a great idea.
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.
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.
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!