This story is over 5 years old.


Graph Isomorphism, You've Been Served

A new algorithm slays a complexity dragon.

Complexity fans and algorithm researchers are excitedly whispering this week about what might be the "the theoretical computer science result of the decade," in the words of MIT professor Scott Aaronson. It has to do with the unsettled complexity of a problem known as "graph isomorphism," which probes the structural similarities between two mathematical graphs, e.g. how well one graph pairs up with another graph component by component.


The current buzz traces back to Laszlo Babai, a theoretical computer science legend based at the University of Chicago. Babai has apparently produced a new algorithm for the graph isomorphism problem that is capable of computing its solution in almost polynomial time.

Polynomial time is, of course, the P in the infamous P vs. NP. For a problem to be solvable in "poly-time" by some algorithm, then if I were to hand that algorithm a number n inputs (n letters in a word, say), it could arrive at a solution in at most nk steps, where k is a constant integer. Poly-time problems can still be enormously complex, but for an arbitrarily large number of input values, the steps required to reach a solution will be relatively reasonable and the algorithm will be relatively "fast."

Relative to what? Exponential time algorithms, mostly. These are the hard tasks, taking at most kn steps, where n is the input and k is some constant. Exponential time problems are the hardest of the NP, or non-deterministic polynomial time, class of problems. Solutions to these problems can be verified by an algorithm in poly-time, but it's unknown if they can be solved in poly-time. This is the P vs. NP question.

Which brings us back to graph isomorphism. It's known that the problem exists in the NP class—that is, a solution can be verified in polynomial time—but whether an algorithm exists that can solve it in poly-time (P) is uncertain. No one has proved that it doesn't exist, but still no one has presented a good solution (though, like many subjects relating to P vs. NP, there are a great many cranks making bad attempts at it).

Babai is far from a crank, however, and has been at this for decades. In 1983, he proved that graph isomorphism could be solved in sub-exponential time (between exponential and polynomial) for some cases, and "moderately exponential" for all cases. Now, it appears that he's shaved off even more complexity and is offering an algorithm that solves the problem in quasipolynomial time, e.g. pretty damn close to poly-time. The details are mostly just gossip at this point—based on this brief abstract—but Babai has scheduled a pair of talks this month describing the new algorithm in greater detail.

Aaronson notes, however, that "as far as I and many others are concerned, it might as well just be in P." That is, the difference between P and where we are now will almost certainly be bridged eventually thanks to some future cleverness. We can just assume it. And whatever future solution that does appear will appease theoreticians rather than engineers, given that several algorithmic approaches currently exist that can solve the problem quickly in most cases, just not in the worst cases.

"Most cases" is usually good enough in the real-world, but unacceptable in the theoretical. Which is sort of just the definition of "theoretical." We'll have more details about Babai's algorithm soon enough.