Via Sarada:

Professor Babai of the University of Chicago recently made an alleged breakthrough in theoretical computer science which concerns the problem of graph isomorphism. In lecture, we have often been told that there are massive networks in biology and social media, to only name two areas, that can not be effectively visualized because of the sheer mass of links and nodes; these networks can grow to be so convoluted that computers occasionally have a difficult time telling if two networks are, in fact, identical or not in an acceptably short time. This is an issue of computational complexity.

There are, for the purposes of this post, two types of problems in computer science. The first are those that can be solved by a computer in polynomial time (P). The second are those whose solution time typically increases exponentially (NP). Some readers may know that this “P vs. NP” problem is one of the “million dollar” Millennium problems offered by the Clay Mathematics Institute. Babai does not claim to have solved the infamous “P vs. NP”; however, any advancement in determining the problems which are “P” or “NP” is important outside the realm of mathematics. Babai’s claim is that he has an algorithm for which telling if two complex networks are the same is completed in polynomial time, making graph isomorphism a “P” problem. If true, then his algorithm could render analysis of any network feasible in a reasonable amount of time.

This has the potential of making many network problems more tractable. Although many network problems must by necessity be done by scratch as they come, like, say, Google assigning PageRank values to pages, other problems may benefit hugely on being able to recognize that part of a current network problem is identical to a different network problem. It would be a waste of time to solve the same, or analogous, problem every time it appeared in an application; an algorithm used in this way could potentially speed up problem solving in any area where massive networks arise.

I believe that any subject that we’ve learned about in Networks is one where this algorithm would prove useful as the given network became very large. It is not very useful to specifically mention one application over another because network analysis is equally important in every large network problem no matter the specific application.

There is some doubt as to whether the algorithm will be practical. Some think that the algorithms currently in use are good enough. I remain hopeful that Babai’s algorithm, if functional, will prove useful. I imagine that as little as 40 years ago, people would scoff at the idea of ever needing to analyze networks with nodes among the millions. Now, of course, we know different. Perhaps in the near future, we will find a use for Babai’s work, if there is not one already.