Very big, *very* exciting news in the theoretical comp sci world today!

A group at HP research has published a proof that, if correct, shows that *the* classic problem of computational complexity has been solved, once and for all. It’s still far from certain that it’s correct. But it’s the most credible attempt that I’ve ever seen, and it’s getting some preliminary favorable feedback from big-names in complexity theory. In fact, one of the *biggest* names in complexity theory, Stephen Cook, has apparently said that it should be taken seriously. If Cook thinks it’s credible, then it’s damn-well credible. It might not be *correct*, but it’s not just crackpottery either.

For the non-CS folks out there, here’s my attempt to explain what the problem is, and what the solution means.

Continue reading →

### Like this:

Like Loading...