Claimed Proof That P != NP 457
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."
Well, shoulders of giants and all (Score:1, Insightful)
As far as I know, this is the first very public proof attempt- its likely it will have flaws, but it may pave the way for someone else or further attempts from the same source even if flaws are found.
Re:Well, duh (Score:4, Insightful)
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.
Re:What would the impacts of this be for cryptogra (Score:1, Insightful)
Re:What would the impacts of this be for cryptogra (Score:2, Insightful)
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.
Funny can cost you karma (Score:1, Insightful)
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
repeat last 3 lines as many times as you like.
Net result: post is +5 funny but you take major karma hits.
Disclaimer: This was true in the early days of funny = no karma boost. They may have fixed it by now. Personally, I think karma should not contribute to karma except to offset overrated or some similar rating designed to indicate "not as funny as it's currently rated."
Re:What would the impacts of this be for cryptogra (Score:5, Insightful)
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.
Re:What would the impacts of this be for cryptogra (Score:1, Insightful)
It's not. Although it might be NP-hard.
Re:formal proof please (Score:5, Insightful)
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?
Re:Funny can cost you karma (Score:3, Insightful)
Correct sir, it should only ever contribute to karma instead.
Re:this is going to create history (Score:3, Insightful)
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?
Re:Well, duh (Score:3, Insightful)
Re:Well, duh (Score:3, Insightful)
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)
Re:Implications (Score:3, Insightful)
Re:I think this is going to take a while. (Score:3, Insightful)
The theory IS simple. P!=NP. Easy.
Proofs, though...proofs can be complicated.
Re:Not in arXiv? (Score:2, Insightful)
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.
Re:this is going to create history (Score:0, Insightful)
It doesn't mean anything about the actual proof, but FLT is easy as pie for damn near anybody above a pretty young age to understand. a^n + b^n = c^n is pre high school mathematics.
The simplest currently known (only) proof of FLT required damn near every scrap of mathematics that's been invented since it was stated which is counter intuitive to people who haven't done much math. In spite of this, the simplicity of the concept allows damn near anybody to get interested in it and make an attempt to solve it.
P ?= NP is more complicated to state and understand meaning that fewer people will even try to find a solution to the question. On top of this, it doesn't have anything like an obvious place to start trying. The one is a simple mathematical equation and a question as to which values for one of the variables allows a solution. The other is an abstract question as to the relative complexity of various algorithms. Night and day as far as the actual nature of the problem.
There are more than enough cases where a simple seeming problem yields an immensely complicated solution ( see Galois Theory and how it solved problems that were around since before Euclid for one cool example) to put that forward as anything like a proof that simple statement implies simple solution, but when the statement is so complicated relative to so many others, it's intuitive to conclude that the proof will take some doing.
Certainly you're fine being skeptical of the OP's statement, but it's not entirely unjustified to suspect although far from justified to conclude what he did.
Re:Well, duh (Score:4, Insightful)
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.
Re:this is going to create history (Score:3, Insightful)
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.