# P != NP maybe proven? **URL:** \ **Category:** Miscellaneous and Personal Stuff I Must Share\ **Created:** [August 9, 2010, 5:21pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733 "2010-08-09T17:21:22Z")\ **Posts on this page:** 11\ **Page:** 3
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [August 12, 2010, 11:32am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/41 "2010-08-12T11:32:54Z")
It isn’t a proof of the proposition. For one, he hasn’t shown how his result isn’t “natural”. Secondly, in the main section, he skims a lot of detail: [QUOTE=Alasdair Urquhart] I agree with most of what Harvey Friedman says about the Deolalikar proof, but I disagree with his statement that the paper is written carefully. I’ve read it through, and in the key places, it has nothing resembling rigorous definitions and proofs. About 75% or more of the paper consists of general remarks or exposition of already known material, and this part is fine. But the key part of the paper, Section 7, where the proof of P eq NP appears, is far from rigorous. The key notion of ENSP model is not clearly defined, but described in a rather rambling fashion, accompanied by a coloured diagram. The crucial Proposition 7.6 does not have a proof at all. Rather, it appears abruptly in the middle of a meandering discussion. The paper reads rather like rough notes stating a plan for settling the question. If Deolalikar wants the community to take his ideas seriously, he needs to write them up in an acceptable way. It’s not the job of the CS theory community to perform exegetical research on what he might have meant. [/quote] Taken from the Foundations of Mathematics (FOM) mailing list. FWIW, there’s a website somewhere with 60 “proofs” for the P=NP problem (false, true, undecidable). What makes this one at least semi-believable is the author’s actually a computer scientist, and not a crank. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [August 12, 2010, 11:40am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/42 "2010-08-12T11:40:32Z")
> [@Indistinguishable](#): > > Well, one thing P = NP would let you do is quickly answer the question “Is there a proof of so-and-so in formal system such-and-such of size less than so-and-such?”. In this sense, Goedel claimed to von Neumann, mathematics would effectively become automated if P = NP; not in that it would become possible to quickly decide whether a statement is or is not provable (this is not in fact generally computable at all), but in that it would become possibly to quickly decide whether a statement does or does not have a proof within such a size as that someone might ever feasibly write it out. So, on that point of view, it would end mathematics as we know it. > > (All this on the usual identification of “quickly” with “polynomial-time”) There’s a really interesting paper somewhere that I remember reading where the author lists all the possible likely outcomes of the P=?NP problem, ranging from the best case where P=NP and we possess an efficient polynomial algorithm for some NP-complete problem, through to the worst case where P/=NP, and various shades in between, and their likely effects on the world. (Perhaps you know it?) > [@Hari Seldon](#): > > Now, no one believed that P = NP, but it was an embarrassment that it is was still open. There’s a few high profile complexity theorists who believe P=NP. R J Lipton is one, for instance. FWIW, his [blog](http://rjlipton.wordpress.com/) has extensive discussions on the recent “proof”. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [August 12, 2010, 12:32pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/43 "2010-08-12T12:32:24Z")
BTW, [here’s](http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper) a crowd sourced critique of the paper. It seems there’s quite a few (potential) problems that have been highlighted. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 12, 2010, 4:17pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/44 "2010-08-12T16:17:04Z")
> [@Giraffe](#): > > Sure, P != NP is not nearly as surprising as a proof that P = NP would be… While almost all computer scientists suspect P != NP is true, a valid proof would still be very surprising. [Here’s a wiki article](http://en.wikipedia.org/wiki/Natural_proof) that hints at some of the intuition that such a proof might be difficult (or even impossible) even if P != NP is true (i.e. that it might be an Undecidable Statement). I clicked on the pdf and saw only “damaged file”, but I’m sure I would have _great_ difficulty understanding it anyway. _However_, if anyone’s “making book” on the matter, for several reasons my money is definitely for the “proof” to be busted. 😃 ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 12, 2010, 4:53pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/45 "2010-08-12T16:53:14Z")
> [@Capt.Ridley\_s\_Shooting\_Party](#): > > What makes this one at least semi-believable is the author’s actually a computer scientist, and not a crank. Yes, that appears to have been the only thing going for it, and not ultimately a reliable indicator of its merits; it seems to have been naught but a load of snowballing hype. Alas… ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 12, 2010, 5:04pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/46 "2010-08-12T17:04:44Z")
> [@Capt.Ridley\_s\_Shooting\_Party](#): > > For one, he hasn’t shown how his result isn’t “natural”. Just to expand on this, one of the main reasons proving P != NP is thought to be hard is because of a number of results demonstrating that certain proof techniques cannot work; for example, Baker, Gill, and Solovay showed that any proof technique settling the matter one way or another would have to contain some step which didn’t scale up to computation augmented with an arbitrary black box “oracle”, and, as **CRSP** refers to, Razborov and Rudich showed that (under another also unproven but widely thought to be true hypothesis in complexity theory) no proof of a particular technical form they call “[natural](http://en.wikipedia.org/wiki/Natural_proof)” can separate P from NP. What makes these results so daunting is that most of the proof techniques known for establishing lower bounds in complexity theory happen to have the properties which these show make them unsuitable for proving P != NP. Accordingly, any serious proposal of a proof that P != NP should presumably come with a clear explanation of how the proof technique clears these hurdles, and, disappointingly, it seems Deolalikar has not provided one. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 12, 2010, 5:07pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/47 "2010-08-12T17:07:12Z")
> [@Capt.Ridley\_s\_Shooting\_Party](#): > > There’s a really interesting paper somewhere that I remember reading where the author lists all the possible likely outcomes of the P=?NP problem, ranging from the best case where P=NP and we possess an efficient polynomial algorithm for some NP-complete problem, through to the worst case where P/=NP, and various shades in between, and their likely effects on the world. (Perhaps you know it?) No, actually; it doesn’t ring any bells for me. But if you remember what it is, I’d be interested in reading it. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [August 12, 2010, 5:15pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/48 "2010-08-12T17:15:13Z")
Russell Impagliazzo, A Personal View of Average Case Complexity. Click [here](http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBIQFjAA&url=http%3A%2F%2Fwww.cs.ucsd.edu%2F~russell%2Faverage.ps&rct=j&q=Impagliazzo%20average%20case&ei=5CtkTLmdC8yQjAe9grXDCQ&usg=AFQjCNEe8zzBjK2IY_r6cYuBvBXCUyR6wA&sig2=KXv-NvuEF0PBkedYcqCJmA&cad=rja). ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 12, 2010, 5:21pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/49 "2010-08-12T17:21:37Z")
Oh, yes, the “five possible worlds”. I’ve heard of this (in discussions where someone says something like “Well, I don’t know about Heuristica, but in Pessiland…” and I say “Huh?” and then they explain…), but never actually read it. Thanks for the link. ---
**Author:** ![Boyo\_Jim](https://avatars.discourse-cdn.com/v4/letter/b/87869e/32.png) [@Boyo\_Jim](https://boards.straightdope.com/u/Boyo_Jim)\ **Post date:** [August 12, 2010, 7:16pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/50 "2010-08-12T19:16:06Z")
P!=NP Proof: Chuck Norris says so! Go argue the point with him. ---
**Author:** ![Animastryfe](https://avatars.discourse-cdn.com/v4/letter/a/8797f3/32.png) [@Animastryfe](https://boards.straightdope.com/u/Animastryfe)\ **Post date:** [August 12, 2010, 7:28pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/51 "2010-08-12T19:28:37Z")
[Here](http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%E2%89%A0np-proof/#comment-5101) is Terence Tao’s attempt at explaining the paper in a high level way. His second iteration is further down the page. [Previous page](https://boards.straightdope.com/t/p-np-maybe-proven/549733.md?page=2)