Algorithm Solves Graph Isomorphism in Record Time

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. On the other hand, graph isomorphism is what computer scientists call a “universal” problem: Every possible problem about whether two “combinatorial structures” are isomorphic — for example, the question of whether two different Sudoku puzzles are really the same underlying puzzle — can be recast as a graph isomorphism problem. In 2012, William Gasarch, a computer scientist at the University of Maryland, College Park, informally polled theoretical computer scientists about the graph isomorphism problem and found that 14 people believed it belongs to P, while six believed that it does not.

Source: www.quantamagazine.org