Home » forums » LtU Forum

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.

By marco at 2015-11-11 16:08 | LtU Forum | previous forum topic | next forum topic | other blogs | 5008 reads

Comment viewing options

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

Hmm.

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.

By marco at Wed, 2015-11-11 16:15 | login or register to post comments

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:

http://www.scottaaronson.com/blog/?p=2521

By Blaisorblade at Fri, 2015-11-13 00:49 | login or register to post comments

Yeah

Yeah, I read that.

By marco at Fri, 2015-11-13 01:41 | login or register to post comments