OMFG

P≠NP

Proof that P=NP would have been much more exciting, of course. But still. Holy crap. We now have proof that not all problems are solvable.^*

(All math problems that is. In most other fields I think we could take that as given.)

A little explanation for the non geeks reading this: there is a set of math problems — the travelling salesman or the knapsack problem are classic examples — which can be solved, and once you have the solution you can verify that solution quickly. But finding the solution in the first place gets exponentially more difficult as the problem gets bigger. Difficult as in, even if you devoted every atom in existence to computing a solution to a traveling salesman problem with a large number of cities, the heat death of the universe would come before you had the answer. So pretty hard, I’m saying.

(There are more practical uses for NP problems than saving a salesman some mileage or sorting a backpack. All modern cryptography is based on NP problems, for example. So the existence of these intractable problems has some useful real-world consequences; this isn’t just abstract sandcastle building.)

Proof that P=NP would have meant that there is a way to solve NP problems in a more realistic timeframe; we just haven’t found that algorithm yet. (And they’re mathematically equivalent problems, so solving any one would mean solving all of them at once.) Instead we have proof that these problems really are irredeemably complex: hard problems really are hard, and always will be.

Which when you put it that way doesn’t sound all that exciting, I know. Emily was sure unimpressed when I tried explaining it to her. But trust me when I say it’s a Big Deal. Not quite this big, but at least this big. Sure, a million dollars isn’t what it used to be, but it’s still pretty good. Also there’s the whole solving-one-of-the-six-most-important-open-questions-in-mathematics thing to go with it. That’s got to be pretty satisfying.

Disclaimers: I am not a mathematician. I understand just barely enough about this stuff to be excited about it; the proof itself is of course completely over my head. And it’s still new, so even real mathematicians haven’t verified it yet, and while everyone seems to agree that this guy isn’t a crackpot (this problem attracts a lot of lunatics, as anything with a million dollar prize attached would) and that the proof looks plausible, some are still skeptical.

In other math news, God’s Number has been proven (by brute force) to be 20, but that seems pretty trivial by comparison. Brute force is boring.