By Lina Sorg
László Babai, a mathematician and computer scientist at the University of Chicago, seems to have successfully simplified the so-called “graph isomorphism” problem, which determines if two graphs (networks of links and nodes) might be the same, even if they look different. Graph isomorphism is considered among the most challenging problems for computers to solve, and Babai’s algorithm supposedly does so much more efficiently than existing approaches. The problem has applications in biochemical data, molecular structures, and complex molecules.
Babai’s work falls under the category of “complexity theory,” a topic that, broadly defined, concerns the ease or difficulty of solving problems with a computer.
Complexity theory attempts to categorize computational problems into two classes based on their difficulty. Simpler problems, such as multiplication of two numbers with n digits each, demand \(n^2\) steps and are placed in class P. Tougher problems, for which finding solutions is often very difficult, demand an amount of steps equivalent to a number to the \(n\)th power, for example \(2^n.\) These are categorized in class NP. \(2^n\) steps is significantly more than \(n^2\) steps, making NP problems more complicated. Ongoing research in complexity theory continues to test how problems in P relate to those in NP.
This is where Babai’s algorithm comes into play. He evidently demonstrates that graph isomorphism and its examination of networks – thought to fall within the harder range of NP – may actually be closer to the simpler P. Networks can be displayed as a collection of points, called nodes, which are connected by straight lines symbolic of interactions between the nodes. As a problem and the corresponding graph grows in complexity, two graphs that have the same connectivity of nodes may look very different. Babai's algorithm can allegedly look at two networks of any size or complexity and determine whether they are the same – and do so in significantly less steps than existing algorithms.
Prior to Babai’s new algorithm, the quickest means of solving the graph isomorphism problem was was the 1983 method published by Babai and Eugene Luks, but the required number of steps grew nearly exponentially with the number of nodes in the networks. In Babai’s algorithm, however, the number of steps increases only marginally quicker than the simplified polynomial time in class P. If Babai’s discovery is true, graph isomorphism – and the difficult problems that stump existing algorithms – might actually be simply and efficiently solved by computers.
Read more about it here.
 |
Lina Sorg is the associate editor of SIAM News. |