Communications of the ACM
Complex Problem Made Simple Sends Computer Scientists Wild
University of Chicago Professor Lszl Babai delivering a lecture in which he claimed that the Graph Isomorphism problem can be solved in quasipolynomial time.
Credit: Jeremy Kun
Theoretical computer scientists are humming with excitement after a potential breakthrough in a long-standing problem called graph isomorphism.
The result could provide a deeper understanding of the nature of computing and "might be the theoretical computer science result of the decade", says Scott Aaronson of the Massachusetts Institute of Technology.
László Babai of the University of Chicago, in a lecture entitled "Graph Isomorphism in Quasipolynomial Time I: The 'Local Certificated Algorithm,'" delivered Tuesday (November 10), described"an algorithm that solves the Graph Isomorphism problem and the related problems of String Isomorphism and Coset Intersection in quaipolynomial time," according to the lecture Abstract.
The result could provide new ways of attacking the P versus NP question.
"It shows a power of algorithms we didn't know before," says Ryan Williams of Stanford University. "In that sense, it's addressing the same kinds of issues we address when we talk about things like P versus NP."
From New Scientist
View Full Article
No entries found