the hot topic in mathematical sciences at the moment is the draft proof that P≠NP (warning: PDF). This is one of the biggest issues in computer science, and one of the Clay Mathematics Institute’s Millennium Problems, so a proof would be Big News in math/CS, and earn the prover a cool $1,000,000. Reaction among blogging theorists is mixed, with some intrigued and at least one willing to bet against it.
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.
For me, it looks good (yes, I’m a mathematician). Obviously, I have not yet checked it in details.
In any case, it’ll be quite an interesting affair, even if this proof is invalid.
If it is right..
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.
Provided it is accepted.
Obviously Pâ NP. That capital N in the middle is a clue. Trust a bloody mathematician not to notice it there.
There have been many proposed proofs (both ways) over the years.
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.
For N=1, sure. Right?
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.
@Massarro:
Thanks for correcting me. I should have waited and taken the 16 hours of sleep first instead of commenting 🙂