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."
I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.
I was a afraid he might have left out an important step.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
If this has appeared somewhere in the other comments, sorry for missing it, but http://xkcd.com/664/ seems oh so appropriate here. (especially the alt text)
I think this is the first time a serious researcher publishes a paper through email. Makes me wonder if he is actually publishing it or just asking for peer-review from his colleagues.
Or maybe he is trying to best Perelman in insanity. After all, even Perelman put the paper in arXiv.
Anyway, about the paper itself; I am a physicist, and he does say correct things about the Ising model and phase transitions. Unfortunately, it is only a small part of his proof that I can grasp. So I think he is dead serious.
Also, nice typography.
entropy happens
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
But the margin is too narrow to contain it.
If you can read this, it means that I bothered to log in.
when I took a graduate level computer science course on randomized algorithms, our professor put up an 8-10 page proof for a randomized algorithm to solve graph coloring problems. near the end of the proof I raised my hand and noted that my professor had made a mistake transcribing a factor, as he had left out one of the paths in a markov chain. after checking the proof my professor realized that in fact the thesis he was using as an example was incorrect. Since that moment, I havent trusted complex mathematical proofs over 15 pages that havent been around for a large number of years. ... I suppose I should come up with some formula for a trustworthiness factor based on length and duration of time it has held up to scrutiny, but my point being, very very few people are qualified to write or debunk this paper, but everybody should be trying to.
Now that, my friend, is +5, Funny. Nothing here has been fixed in years.
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
NP-class problems can be translated into minesweeper puzzles. The problem is determining whether a solution exists in polynomial time. Your example is not solvable. The problem is determining whether a solution can be determined for arbitrarily large puzzles in a polynomial-scale algorithm, or whether the amount of time needed basically grows exponentially. This guy is saying that it grows basically exponentially.
See here for a more complete explanation: http://www.claymath.org/Popular_Lectures/Minesweeper/
We'll know that P != NP if it takes us less time to verify the proof as it took him to generate it.
Even if P=NP, polynomial solutions requiring time n^99 consume enough time to be practically infeasible. Thus, even P=NP would not harm cryptography much, if it did not provide very efficient solutions for every NP-hard problem. On the other hand, favorite cryptographic hard problems, such as factoring, are not known to be NP-hard and may well turn out to be solvable in polynomial time, even if P!=NP. Therefore, proof that P!=NP won't have any interesting implications for cryptography unless it contains new ideas that can help in other ways. Neither will proof P=NP unless it includes ideas for fast solutions of interesting problems, such as fast factoring or fast discrete logarithm. Proof of P!=NP may help to solve another interesting problem in cryptography: one-way functions. Right now many results are built on the assumption that such functions exist, but nobody have found a single provable one-way function (easy to compute, infeasible to reverse). A bunch of functions are believed to have this property, but not a single one has been proved difficult to reverse. I would be interested to see if this proof will produce such an animal - a provably one-way function.
Sorry, I wasn't clear. I meant what's the next big problem in computer science.
Assuming this proof holds up, the next set of questions are how much the complexity hierarchy breaks down. There are a host of complexity classes between P and NP. Other important classes include PP and BPP http://en.wikipedia.org/wiki/BPP, http://en.wikipedia.org/wiki/PP_(complexity). BPP is a subset of NP and is tentatively believed to be equal to P. Another important class is BQP http://en.wikipedia.org/wiki/BQP which is the class of problems which can be solved quickly by a quantum computer. If this proof goes through it may generalize to showing that some of these other classes are distinct (proving that BQP is not equal to P would be almost as big a deal as proving that P !=NP).
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
Oh man, if you think the politics and backbiting are bad in typical academia, wait until you see an entire computer science department arguing over who gets to have illicit sex in order to set off the proof-generating team.
"This algorithm runs in constant time. Come on, 2,147,483,648 is a constant..."
Being a researcher in Finite Model Theory (FMT) this paper is very interesting because it uses ideas from that area, i.e. the LFP(FO) bits. Reading through the proof synopsis and scanning the FMT sections there are several potential pitfalls:
It is already known that LFP(FO) on unordered structures is a proper subset of LFP(FO) on order structures, so if the ordering and order-invariant requirements for LFP(FO) = P are not dealt with in the proof, then all the author has done is proof that LFP(FO) on unordered structures is a proper subset of NP. Which is already known.
Another potential problem is in the arguing that all first-order properties are local (Hanf's Theorem) in the presence of ordering, as every vertex is effectively connected to every other vertex (Immerman's proof of LFP(FO) = P requires total ordering of the underlying graph/structure), and hence every vertex is in the radius = 1 neighbourhood of every other vertex.
The crucial step in the proof, appears to be the argument that no LFP(FO) formula can extend a partial solution to k-SAT to a full solution to k-SAT. This is where I'd check the logical steps of the proof, and also make sure that the ordered nature of LFP(FO) structures is correctly considered.
I look forward to seeing this published in a peer-reviewed mathematics journal: I'd recommend to the author the "Journal of the ACM" for this (as it's one of the best journals in the field).