So what do I think of the proof? Honestly, this is so far out of my areas of competence that I need Google to remind me what the symbols mean. About all I know is that it’s a Big Deal in computer science. Putting that together with the only other thing I know about computer science, though, namely that it’s a Web N.0 (for N > 1) world these days, and we’re all open-y citizen-y crowdsource-y scientists now, we can settle this question right now with the Magic of the Internet:

The results of the first 48 hours of voting will be legally binding, as far as you know, so choose wisely, and/ or lobby lots of people to vote for your favorite choice.

then just like when the proof to Fermat’s theorem was accepted rigorously and I very slowly taught myself enough group theory and read the literature so that I could understand the proof, I will probably spend the next year or two of free time teaching myself (which is even farther afield than what I normally encounter) so that I can understand this proof.

Ugh to sleep deprived at the moment to be able to comprehend even the references but I really hope they got it this time.

@Bob: I got started with computational complexity theory learning how to prove that 1+1 = 2. No joke.
The proof, if valid, means more then the obvious P≠NP. One of the most immediate and practical applications of the proof would be that the time for attacking a public key cryptography algorithm (like RSA), if no other weaknesses are present, cannot be reduced below the time it takes to factor they key.

And there are several thousand other algorithms, that we think/know are NP, for which this proof basically states we will find no short-cut that allows us to solve them faster.

@who cares: Factoring is not known (or believed) to be NP-complete. It’s not currently proven that it’s actually outside P or NP-complete (as most people believe). So a proof that P!=NP would not necessarily mean anything about the feasibility of breaking RSA.

There *are* encryption schemes that rely on the hardness of running algorithms that are known to be NP-hard, but they are not in widespread use.

Here is roughly the analogy from computer science to physics, assuming the proof is true:

Assume that some new, subtle result in string theory came out. One of the implications of this new string theory result is that all the weird exotic impractical FTL schemes (like the Alcubierre drive) aren’t just impractical, they’re flatly impossible. All of them. None of them work. The speed limit is the speed limit.

This is going to be of deep interest– reading the result, understanding the result, building off the result– to only a very small number of people, even in the physics community. It will be of shallow interest to a wider community of physicists, who might poke around it in a hobby sense, or a curiosity sense, or to see how there’s some interaction with their own specialty, before realizing that there probably isn’t. And for the rest of the world, the world today is the same as it was yesterday, because all you’ve done is closed a few loopholes that very few people thought were actually viable, anyway.

That’s more or less what this is: the world today is as computationally difficult as it was yesterday.

(As for whether it’s true, I’ll wait until some postdoc team translates it into coq and machine-verifies it, and gets the translation certified and peer reviewed.)

abb3w’s link to that website listing 60 proofs, half claiming P=NP, the other half proving P=/=NP, with a number of “can’t determine” sprinkled in for good measure, is so enlightening. It looks like it’s a rich field to put something on arXiv, and wait for someome to figure out if you’re right.

I haven’t read the paper and probably don’t have the background to understand it all, but from what I hear from others, the attempted proof suffers from a fatal flaw that has plagued many attempts to prove P != NP: it would imply that certain problems are hard that are known to be easy, such as 2-SAT and XOR-SAT.

Eureka: Discovering Your Inner Scientist will be published in December 2014 by Basic Books. "This fun, diverse, and accessible look at how science works will convert even the biggest science phobe." --Publishers Weekly (starred review) "In writing that is welcoming but not overly bouncy, persuasive in a careful way but also enticing, Orzel reveals the “process of looking at the world, figuring out how things work, testing that knowledge, and sharing it with others.”...With an easy hand, Orzel ties together card games with communicating in the laboratory; playing sports and learning how to test and refine; the details of some hard science—Rutherford’s gold foil, Cavendish’s lamps and magnets—and entertaining stories that disclose the process that leads from observation to colorful narrative." --Kirkus Reviews Google+

How to Teach Relativity to Your Dog is published by Basic Books. "“Unlike quantum physics, which remains bizarre even to experts, much of relativity makes sense. Thus, Einstein’s special relativity merely states that the laws of physics and the speed of light are identical for all observers in smooth motion. This sounds trivial but leads to weird if delightfully comprehensible phenomena, provided someone like Orzel delivers a clear explanation of why.” --Kirkus Reviews "Bravo to both man and dog." The New York Times.

How to Teach Physics to Your Dog is published by Scribner. "It's hard to imagine a better way for the mathematically and scientifically challenged, in particular, to grasp basic quantum physics." -- Booklist "Chad Orzel's How to Teach Physics to Your Dog is an absolutely delightful book on many axes: first, its subject matter, quantum physics, is arguably the most mind-bending scientific subject we have; second, the device of the book -- a quantum physicist, Orzel, explains quantum physics to Emmy, his cheeky German shepherd -- is a hoot, and has the singular advantage of making the mind-bending a little less traumatic when the going gets tough (quantum physics has a certain irreducible complexity that precludes an easy understanding of its implications); finally, third, it is extremely well-written, combining a scientist's rigor and accuracy with a natural raconteur's storytelling skill." -- BoingBoing