Erica Klarreich in 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.”
More here.
