Rumors in Complexity Theory

I imagine everybody already has read this, and that there's nothing to discuss really. Nothing to do but wait, but I think it should be an LtU post anyway.

For days, rumors about the biggest advance in years in so-called complexity theory have been lighting up the Internet. That’s only fitting, as the breakthrough involves comparing networks just like researchers’ webs of online connections. László Babai, a mathematician and computer scientist at the University of Chicago in Illinois, has developed a mathematical recipe or "algorithm" that supposedly can take two networks—no matter how big and tangled—and tell whether they are, in fact, the same, in far fewer steps than the previous best algorithm.

From Science Magazine.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


I guess the best case scenario would be not a breakthrough in P versus NP, but if this approach generalizes. I.e., they can simplify NP problems that far down that the exponential influence becomes really small, and the question becomes obsolete for most practical problems.

Not holding my breath though.

No P vs NP

This is about graph isomorphism, which has been very hard to solve, but was never proved to be NP-complete. IIUC, this doesn't even help directly with other NP-complete problems. The source of Scientific American is Scott Aaronson, so here's the source directly:


Yeah, I read that.