Home → Careers → Complex Problem Made Simple Sends Computer Scientists... → Full Text

Complex Problem Made Simple Sends Computer Scientists Wild

By New Scientist

November 13, 2015

[article image]

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