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

An unreadable sentence

[Anonymous Coward]

Maybe it is just me, but "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" doesn't make sense to me no matter how I read it.

Re: An unreadable sentence

[Anonymous Coward]

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

[behrooz0az]

Because it's not one sentence:

The new algorithm places the problem of graph isomorphism as, at most, just barely above P.

P is not his first name:D

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

Re:An unreadable sentence

[Anonymous Coward]

Your brain, have it checked. It might need its weekly scotch refill.

Re:An unreadable sentence

[Anubis IV]

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.

Re: An unreadable sentence

[bill_mcgonigle]

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:An unreadable sentence

[neoritter]

Is that why you have one space after your sentences? Never mind the double space has been effectively pushed out of grammatical styles.

Re:An unreadable sentence

[Anubis IV]

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.

Re:An unreadable sentence

[michelcolman]

How can something be closer to P than to NP? P is a subset of NP.

You mean NP-complete, right?

Re:An unreadable sentence

[Anubis IV]

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:An unreadable sentence

[Kinthelt]

I stubbornly still use double spaces after sentences.

Re:An unreadable sentence

[neoritter]

I do it out of spite sometimes when writing a paper. I got dinged for it so much in school.

Re: An unreadable sentence

[Samantha Wright]

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.

Re:An unreadable sentence

[amRadioHed]

/. 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:An unreadable sentence

[Anonymous Coward]

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

Hey Laszlo, how about just present the actual algorithm for peer review, instead of SKETCHED OUT.
Sounds like a wannabe that's trying to sketch/stake out Prior Art.

Re: An unreadable sentence

[slew]

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.

Re:An unreadable sentence

[smallfries]

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:An unreadable sentence

[michelcolman]

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: An unreadable sentence

[Samantha Wright]

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.)

Re:An unreadable sentence

[flink]

It's not just /. HTML compresses consecutive spaces when rendering unless you explicitly use non-breaking spaces.

Re:An unreadable sentence

[neoritter]

*WOOSH*

Person comments on lack of double spaces in HTML formatted text. Proceeds to lack double spaces in his HTML formatted text.

Re: An unreadable sentence

[neoritter]

Did you reply to the wrong person?

Re: An unreadable sentence

[Samantha Wright]

No; I'm afraid I'm just that boring.

Re: An unreadable sentence

[neoritter]

It wasn't that it was boring. It just seemed out of place given my preceding comment.

Re: An unreadable sentence

[Samantha Wright]

My thinking was that you might like to be able to place your habits in an historical context, what with the spite and all.

Genetic alignments?

[Anonymous Coward]

I know that some genetic alignment algorithms rely on graph theory, but unfortunately lack the mathematical skills to fully understand them, does anyone have enough skills in the subject to comment on whether this might be applied to such problems.

Re: Genetic alignments?

[Anonymous Coward]

Not hardly.

Re:Genetic alignments?

[KGIII]

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.

Re: Genetic alignments?

[Anonymous Coward]

AFAIK the question for alignment has been how you do it efficiently, not what its complexity class is. Most alignment tools I've worked with are close to linear time.

Re:Genetic alignments?

[Anonymous Coward]

> I know little to nothing about genetics nor their alignment

If genetics was plural it would have an apostrophe like physic's does.

Re:Genetic alignments?

[Anonymous Coward]

Hmm... I'm not sure I'll remember that but thank you. It makes sense. I'm talking about the genetic's alignment. When writing it, I did not really think of it that way - not as a possessive so much but certainly as a plural. Are you sure it's still genetic's when I say something like "the genetics researcher's data was...?"

I'm always making an effort to improve my writing, it's something that I've worked at for a long time. I'm not entirely sure you're correct that it is plural in that case. We don't say, "the laws of physic's" with an apostrophe - or do we? Hmm...

I'll check this later - it's obviously me. My VPN did let me post logged in a minute ago but now is preventing me from doing so. At least, I think it's the VPN.

Interesting

[Tyler Durden]

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.

Re:Interesting

[Anonymous Coward]

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:Interesting

[Anonymous Coward]

I use a tool called NAUTY every night. I searches the interweb for NAUTY pictures and videos.

Isomorph?

[Anonymous Coward]

That's what they hunt in aliens...?

Re:Isomorph?

[ClickOnThis]

http://www.lmgtfy.com/?q=isomo...

Re:Isomorph?

[halivar]

No, you're thinking of xenomorphs. Isomorphs are the miracle AI folks hunted by C.L.U. 2.0.

Re:Isomorph?

[Anonymous Coward]

All from the Greek:
"Iso-" = "equal"
"-morph" = "form, shape"
"Xeno-" = "foreign, strange, alien"

So, isomorph = equal shape, xenomorph = alien [life]form.

Re:Isomorph?

[Anonymous Coward]

All from the Greek:
"Iso-" = "equal"
"-morph" = "form, shape"
"Xeno-" = "foreign, strange, alien"

So, isomorph = equal shape, xenomorph = alien [life]form.

Tom Baker's Doctor Who referred to the controls of the TARDIS as being Isomorphic, in that context meaning that the controls only responded to him. I see from this definition here the TARDIS just switches the labels of the controls around for other people. So Rose Tyler or Clara Oswald or Sarah Jane Smith could fly the TARDIS if they just knew what the controls actually were. (and could do multi dimensional vector calculus in their head.) There is the big take off lever.. that is pretty obvious... the old series the door and screen controls were pretty easy to remember too.

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?

Re:It's been a while

[nrjyzerbuny]

I believe that Subgraph Isomorphism is NP-Complete, but Graph Isomorphism is not.

Re: It's been a while

[Anonymous Coward]

No, it's one of the problems in NP that have neither been proven to be in P nor to be NP-conplete.

Re:It's been a while

[Anonymous Coward]

Subgraph isomorphism trivially encodes k-Clique and Hamiltonian Path, so you're most certainly correct.

Re:It's been a while

[Anonymous Coward]

Nope. According to wikipedia, it's not known wether it is P or if it is NP-C.

Re:It's been a while

[Anonymous Coward]

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 state of mathematics isn't even capable of describing the solution because you have to know what type of the infinite number of NP problems there are and discern a non-exponential-time (P) solution for them one-at-a-time. Take an array of 8 numbers, determine if any 3 equal another number - the straight-forward solution is to cross reference every set of 3 and perform the check (in exponential time as n*n or n*n*n) but you might just as easily find a solution in polynomial type (something like n log n log n) by splitting the total set into subsets following a binary-tree pattern and doing some interesting things in the logical side otherwise. In that situation you've taken half the problem and wrapped it up into the logic of the solution in a way that is so completely context-specific as to be useless to "how do I make it float?" and most other NP problems.

Re:It's been a while

[careysub]

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:It's been a while

[Anonymous Coward]

People have serious mis-conceptions about the relationship between cryptography and mathematically hard problems.

The only place they even get close is in "trapdoor functions". Symmetric crypto doesn't use such functions, it's exactly as hard to encrypt or decrypt AES-256 so there is no "trapdoor", you either know the 256-bit key, or you don't, and if you don't the best known attack is to try all possible 256-bit keys, hypothetical breakthroughs in complexity change nothing there.

As to trapdoor functions used in public key crypto like RSA, it depends on the specific function. Some are thought probably related to an NP problem, others are certain to be, still others it's totally unclear. Moreover, while mathematicians are interested in theoretical limits, the trapdoor functions are used in a practical way. Suppose you discover a brilliant way to crack any length of RSA key, it only needs one thousand years of setup, and 40 exabytes of storage then it works on any keys. Well, this is not a practical attack on RSA, but Mathematicians are satisfied that in principle it's an O(1) algorithm.

Re:It's been a while

[Anonymous Coward]

Your ideas intrigue me, and I would like to subscribe to your newsletter.

Re:It's been a while

[canajin56]

The "God-like creative power" comes from simplifying "P=NP" as "it's as easy to recognize a correct answer as it is to come up with one". I've seen people then go from this simplification to "proving" that P!=NP because "it's harder to write a song than to listen to it". It's nonsense for a lot of reasons. The most striking is the assumption that for every single mental task that humans attempt, we always use the absolute most efficient algorithm in all of existence. Reversing that to say that "proving P=NP proves that it's easy to create artistic works (and proving something is possible gives you the power to do it instantly)" is new to me though.

Re:It's been a while

[Anonymous Coward]

Ah, but you forgot that the Mackaski-Bazier point isn't invariant under isomorphic transforms, resulting in a discontinuity at the 4th level.

Re:It's been a while

[Anonymous Coward]

Your ideas intrigue me, and I would like to subscribe to your newsletter.

It is called CSI: Cyber

Re: It's been a while

[Anonymous Coward]

Is this supposed to be a joke or are you and the GP saying something meaningful that is just beyond comprehension?

Re: It's been a while

[Anonymous Coward]

"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."

You do not know that, so don't state it like it is fact. What you are trying to say is that it will most likely be non-constructive. Yet, I do not think we know that either. It is best to keep all options open at this point. It is entirely possible someone could find a large exponent polynomial time algorithm to prove P=NP.

Direct applications

[Krishnoid]

Any examples of direct/proximate applications to layperson problems?

Re:Direct applications

[Anonymous Coward]

Optimisation of graphs and subgraphs (networks, programs etc are all graphs, programs are a DECISION FLOW graph of deterministic operations, useful also for unit test generation using branches to determine minimum useful test cases for a function).

Don't forget a graph is also made up of sub-graphs. MANY MANY problems can be represented as graphs at the abstract level.

Re:Direct applications

[Anonymous Coward]

Three off the top of my head.

Part layout on a circuit board and shortest path determination culling. Culling of chess layouts for depth searching best moves in a chess game.

Think of it as a faster way to say 'I already looked at these paths' but this one 'looks different' but is it *really* different. If the searching thru a particular tree is expensive this can be a good way to throw away results so you do not do 2x the work. It comes at a cost though.

Think of it as a jumble of points with random connectors between them. Two people create the same 'set' but is it the same set? maybe.

Re:Direct applications

[JoshuaZ]

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.

Re:Direct applications

[gweihir]

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:Direct applications

[Krishnoid]

'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:Direct applications

[Anonymous Coward]

No. Expect this to maybe have an impact during the next 100 years or so.

Except this is an algorithm that is used now and improvements can have immediate impact. A lot of math does have immediate impact. And for many things that don't, more of often than not in my experience, mathematicians are doing it because of interest in pure study, not because they are hoping for some long term impact.

Re:Direct applications

[tlhIngan]

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.

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 line has a problem it solves neatly and practically. But we just don't know what it is yet.

3) A use crops up unexpectedly and in a surprising place. History is full of such happenstances where two unrelated fields suddenly converge unexpectedly

That's why you do pure research without industry uses - because what you discover might not be useful to industry now, but may become a cornerstone later on.

Re:Direct applications

[frank_adrian314159]

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:Direct applications

[njnnja]

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:Direct applications

[Anonymous Coward]

Certainly. Suppose you have a couple of abstract graphs lying around and you want to know if they're isomorphic. You can use this result to finish the job in (1,000,000,000)n years instead of (1,000,000,000)n^2 years. You're welcome!

Re:Direct applications

[smallfries]

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:Direct applications

[JoshuaZ]

We don't actually have a proof that group isomorphism is in P, and we don't also know whether this new work will help at all with that problem. One might hope that one could take a pair of groups, convert them to the relevant graphs and then run this, but that's unlikely to be helpful since we already have group isomorphism algorithms that work in quasipolynomial time- in fact the most obvious non-trivial one does so. Note also that in the case of the groups arising from Diffie-Hellman and similar procedures, we know exactly what the groups are isomorphic to. They are in fact easy to write down Abelian groups and knowing precisely what the groups are is necessary for the cryptographic algorithms to work. So there's no obvious way that this sort of thing helps there.

Re:Direct applications

[Anonymous Coward]

You can represent a group with a graph structure by defining elements as vertices and elements that can be reached in a single operation from one another as edges. That said, graphs can represent many other things - countries and sharing a border for the purposes of the famed Four Color Theorem, circuit diagrams, social networks, etc.

Re:technobabble

[BarbaraHudson]

Please check your calendar. Today is not Troll Tuesday.

Re:technobabble

[zlives]

you clearly are not familiar with Troll Goodness Its Friday.

also i thought it rated more funny than anything else :)

Typo: ... determining when graphs are isomorphic.

[Anonymous Coward]

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

Nice to see technical stuff on /. again

[mveloso]

It's been a while since I've seen a story I didn't understand on this site. Keep up the good work!

Re:Nice to see technical stuff on /. again

[DoofusOfDeath]

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.

Re:Nice to see technical stuff on /. again

[Anonymous Coward]

Sexist!

P vs. NP is not that important for crypto

[gweihir]

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!

Re:P vs. NP is not that important for crypto

[Anonymous Coward]

what the fuck is Omega? learn your fucking math, forget the heresy Knuth&Co or whoever the fuck wrote it!

it is Ordnung(n). Read Landau you fuck!

Laszlo!

[yodleboy]

Laszlo! The finest mind of his time!

Marks

[Matheus]

I thought you could easily identify them by the cool marks on their arms??

Re:Typo: ... determining when graphs are isomorphi

[JoshuaZ]

Yes, and in the title isomorphism is spelled wrong also. Not my best submission.

Finite simple groups?

[Anonymous Coward]

Of order two?

https://www.youtube.com/watch?v=UTby_e4-Rhg

P is in NP

[Anonymous Coward]

P is in NP (P is a subset of NP). NP is a class of problems where a polynomial time certifier exists. The answers to all problems in P can be verified in polynomial time. Pretty sure this should read that the problem lies somewhere between NPC (NP-Complete) and P (Polynomial). Btw, NPC is in NP as well.

Re:technobabble

[KGIII]

Ah - but it *is* SJW Friday! It's a bit of a toss-up. I'm not quite sure where it belongs.

Relation to cryptography

[Kickasso]

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.