Landmark algorithm breaks 30 year impasse

[Sabre]

Wired

A THEORETICAL COMPUTER scientist has presented an algorithm that is being hailed as a breakthrough in mapping the obscure terrain of complexity theory, which explores how hard computational problems are to solve. Last month, László Babai, of the University of Chicago, announced that he had come up with a new algorithm for the “graph isomorphism” problem, one of the most tantalizing mysteries in computer science. The new algorithm appears to be vastly more efficient than the previous best algorithm, which had held the record for more than 30 years. His paper became available this week on the scientific preprint site arxiv.org, and he has also submitted it to the Association for Computing Machinery’s 48th Symposium on Theory of Computing.

For decades, the graph isomorphism problem has held a special status within complexity theory. While thousands of other computational problems have meekly succumbed to categorization as either hard or easy, graph isomorphism has defied classification. It seems easier than the hard problems, but harder than the easy problems, occupying a sort of no man’s land between these two domains. It is one of the two most famous problems in this strange gray area, said Scott Aaronson, a complexity theorist at the Massachusetts Institute of Technology. Now, he said, “it looks as if one of the two may have fallen.”

Babai’s announcement has electrified the theoretical computer science community. If his work proves correct, it will be “one of the big results of the decade, if not the last several decades,” said Joshua Grochow, a computer scientist at the Santa Fe Institute.

Computer scientists use the word “graph” to refer to a network of nodes with edges connecting some of the nodes. The graph isomorphism question simply asks when two graphs are really the same graph in disguise because there’s a one-to-one correspondence (an “isomorphism”) between their nodes that preserves the ways the nodes are connected. The problem is easy to state, but tricky to solve, since even small graphs can be made to look very different just by moving their nodes around.

Now, Babai has taken what appears to be a major step forward in pinning down the problem’s difficulty level, by setting forth what he asserts is a “quasi-polynomial-time” algorithm to solve it. As Aaronson describes it, the algorithm places the problem within “the greater metropolitan area” of P, the class of problems that can be solved efficiently. While this new work is not the final word on how hard the graph isomorphism problem is, researchers see it as a game changer. “Before his announcement, I don’t think anyone, except maybe for him, thought this result was going to happen in the next 10 years, or perhaps even ever,” Grochow said.

There are quite a few uses for this, from industry to intelligence. It will be interesting to see who buys rights to the IP first!