P != NP maybe proven?

[Capt.Ridley_s_Shooting_Party]

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:

@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.

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.

[Capt.Ridley_s_Shooting_Party]

@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 has extensive discussions on the recent “proof”.

[Capt.Ridley_s_Shooting_Party]

BTW, here’s a crowd sourced critique of the paper. It seems there’s quite a few (potential) problems that have been highlighted.

[septimus]

@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 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.

[Indistinguishable]

@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…

[Indistinguishable]

@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” 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.

[Indistinguishable]

@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.

[Capt.Ridley_s_Shooting_Party]

Russell Impagliazzo, A Personal View of Average Case Complexity. Click here.

[Indistinguishable]

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.

[Boyo_Jim]

P!=NP

Proof: Chuck Norris says so! Go argue the point with him.

[Animastryfe]

Here is Terence Tao’s attempt at explaining the paper in a high level way. His second iteration is further down the page.