Slashdot Mirror
Claimed Proof That P != NP
morsch writes "Researcher Vinay Deolalikar from HP Labs claims proof that P != NP. The 100-page paper has apparently not been peer-reviewed yet, so feel free to dig in and find some flaws. However, the attempt seems to be quite genuine, and Deolalikar has published papers in the same field in the past. So this may be the real thing. Given that $1M from the Millennium Prize is involved, it will certainly get enough scrutiny. Greg Baker broke the story on his blog, including the email Deolalikar sent around."
Ohhhh my god, someone modded this insightful.
Okay... sometimes when it's really really really obvious that something's a joke, it's okay to play along and make mock serious follow ups and even *gasp* non-serious moderations. This works on the basis that it's obvious that both the original poster and the modder are joking.
It means we can breathe easy that a lot of crypto out there is now provably secure.
Wrong. It doesn't prove that there is no faster factoring algorithm.
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify.
I think it's important to realize that even if they are "unresolved problems" of mathematics, it's not like both answers are equally likely like the flip of a coin. For example the Riemann hypothesis states that all non-trivial zeros of the Riemann zeta function have real part 1/2. It's true for every non-trivial zero we've ever found, but it's not proven true for all the infinitely many zeros. However, outside of mathematics a proof it's true will be met with "yeah, that's what we thought" and a proof it's false with "OMG what's going on here?". Another example is the prime twin conjecture, are there inifinte pairs like (3,5) (5,7) (11,13) (17,19) and so on. There's very good reason to believe it's true but nobody has able to formally prove it. There's a lot of problems today that appear to support the idea that P != NP, and that's what most people believe the answer is. However, stringing together formal proof that it's so is much harder. If this paper turns out to be true, surely it's a great leap for mathematics but it's the answer that doesn't change the world.
Live today, because you never know what tomorrow brings
Are you raving mad?
Of course there will be an error with this proof. Many errors, actually. Most of them irrelevant.
Maybe one of them is not. You know what? It will be caught in peer-review, exactly as it's been happening in the last centuries.
There's a reason noone uses formal proofs in mathematics. They're dull. They're slow. And we trust peer-review (for correctness, anyway).
What would be the use of a proof that no human can understand?
entropy happens
Correct sir, it should only ever contribute to karma instead.
Invaders must die
On what basis can you claim that P=NP is slipperier, given that FLT took 360 years to prove, and we've only been on it for 70 odd years so far?
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
But ACs can't bank karma. I guess someone had mod points to burn.
Yeh, I get moded as a troll all the time!
I've mearly been hanging around a little to long, and have grown to post more dry humour, feeling it a little more insightful that just repeating the contents of the past 10 years of ./ posts.
the smelling old grandma Nazis are still around though!.
Please, remind me of Godwin's law again.
What is it again, the more repressive that the indoctrinated members of society become against a topic controversial (with them) enough that it leads to a longer and longer discussion on the internet. The greater the chance that people begin to realise that that not to dissimilar to cultural and other oppression as faced under the Nazis. (by the Gypsies, disabled, polish oh and some other people who didn't do too badly out of it)
thank God the internet isn't a human right.
Not much, really. P != NP was the widely expected answer, it was just an unproven assumption. The fields that are affected have been proceeding as if P != NP was correct.
The theory IS simple. P!=NP. Easy.
Proofs, though...proofs can be complicated.
This isn't a "publication" at all. It's a researcher circulating a draft among his colleagues for comments before he makes it publicly available somewhere like the arXiv. And for a long solution to a major problem like P=NP, having a few trusted people check for obvious flaws before you share it with the world is a lot saner than you seem to think.
So apparently if something sounds technical and you don't know what it is you assume it is nonsense?
Only when spoken by politicians, CEO's or in a TV drama.
Ah, but there are more of us now. If it took 1 billion people 3650 years to solve, it should take 6 billion people a mear 60 years. The fact it has take 70 already clearly shows the added cycles this calculation requires.
Humanity follows basically the same logic as massively parallel supercomputers.