P ≠ NP

Several points on the question of whether the proof is likely to be correct:<p>* As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it <i>was</i> circulated and someone other than the author made it public.)<p>* Therefore a proper assessment is going to take a while. Until then we can only speculate :-)<p>* While the crank attempts at P =? NP are statistically much more common (<a href="http://news.ycombinator.com/item?id=347295" rel="nofollow">http://news.ycombinator.com/item?id=347295</a>), this isn't one of them. The author is a legit computer scientist: <a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/" rel="nofollow">http://www.hpl.hp.com/personal/Vinay_Deolalikar/</a><p>* On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag.<p>* Looking at his papers, it's possible he's been working on this for about 5+ years -- he has two threads of research, basic and industrial, and the former line of publications dried up around 2004.<p>* On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago.<p>* It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (<a href="http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf" rel="nofollow">http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf</a>). Mulmuley's plan of attack involved algebraic geometry.<p>* This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment <a href="http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#comment-1260" rel="nofollow">http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c...</a> which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)<p>* If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier.<p>* Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a "theorem" in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning.<p>* If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking.<p>Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.

The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail:<p>Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP<p>Dear Fellow Researchers,<p>I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.<p>The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.<p>This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.<p>This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.<p>Comments and suggestions for improvements to the paper are highly welcomed.<p>Sincerely,<p>Vinay Deolalikar Principal Research Scientist HP Labs<p><a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/" rel="nofollow">http://www.hpl.hp.com/personal/Vinay_Deolalikar/</a>

102 pages via one of the most annoying PDF readers on the planet? No thanks.<p>There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.

Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct:<p><a href="http://scottaaronson.com/blog/?p=456" rel="nofollow">http://scottaaronson.com/blog/?p=456</a>

I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof):<p>"The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound."<p>How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?

Here's a list of many other proofs for the P vs NP problem: <a href="http://www.win.tue.nl/~gwoegi/P-versus-NP.htm" rel="nofollow">http://www.win.tue.nl/~gwoegi/P-versus-NP.htm</a>

Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS.<p>Edit: As someone else pointed out a few minutes ago <a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/" rel="nofollow">http://www.hpl.hp.com/personal/Vinay_Deolalikar/</a> confirmations began arriving today. How soon before Vinay has a Wikipedia entry? For those who are qualified to evaluate this, I suspect a consensus as to validity will develop within weeks if not days. If thumbs up, he must be worthy of one of the outstanding large-cash-value math prizes. Perhaps even the Nobel?

His personal home page <a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/" rel="nofollow">http://www.hpl.hp.com/personal/Vinay_Deolalikar/</a> seems to have been updated.<p>"Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned. "

I've not seen any discussion of his paper yet, but the author has an impressive CV:<p><a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/" rel="nofollow">http://www.hpl.hp.com/personal/Vinay_Deolalikar/</a>

Bummer! It's like proving conclusively that the tooth fairy, Santa and the Easter bunny definitely don't exist.

While the author of this paper does not appear to be a crank, nowhere in the entire paper does it discuss why the fundamental barriers of naturalization, algebrization, and relativization don't apply to the work, making it seem unlikely that those barriers have actually been overcome.

I'd like to say congratulations to Vinay Deolalikar for getting to this point and putting the paper out there. As randomwalker and others have said, this appears to at least be a legitimate attempt. It must take some seriously thick skin to work on a paper that a) is in an area so full of failed attempts and error filled proofs; and b) that EVERYONE is going to read and try to tear apart.

We created a prediction market for the next winner of the Clay Prize here <a href="http://smarkets.com/current-affairs/clay-prize/next-winner" rel="nofollow">http://smarkets.com/current-affairs/clay-prize/next-winner</a>

WOW.<p>Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal.<p>As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof.<p>Read the "Consequences of Proof" section in the Wikipedia article here: <a href="http://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow">http://en.wikipedia.org/wiki/P_versus_NP_problem</a><p>[edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is already sort of assumed.

At least for this, we should have a reddit like system for peer reviewing, so that comments from all reviewers can be seen by everyone.

Some background on the P ≠ NP problem:<p><a href="http://en.wikipedia.or/wiki/P_versus_NP_problem" rel="nofollow">http://en.wikipedia.or/wiki/P_versus_NP_problem</a><p><a href="http://www.claymath.org/millennium/P_vs_NP/" rel="nofollow">http://www.claymath.org/millennium/P_vs_NP/</a>

Anyone got a link to any proper discussion?

I think that whether P is NP or not could turn out to be undecidable and in fact one could add either equality or inequality as an independent axiom. The theory of computational complexity is about asymptotic results as the size of the instances goes to infinity and involves `there exists` statements whose meaning when applied to infinite sets is typically ambiguous. For instance, it turned out to be a matter of choice whether or not you want the set of all subsets of real numbers between zero and one to equal or to be strictly larger than the set of so called measurable sets. And whether or not a set is measurable can be characterized in a very concrete way about the possibility of approximating it by unions of intervals. So the question of whether or not there exist non measurable sets turned out to depend on `what you mean by set`in a way which people hadn´t thought about before. I suspect the question whether or not P is NP will depend on what we mean by P and NP in ways which so far no one thought about.

I think this is getting unwanted publicity. The author never released the proof in public or made any announcement. He only sent it to his expert friends so that they can point out potential flaws. May be this needs more research and putting him in spotlight is not helping anything.

Why isn't this in a peer-reviewed journal?

So: What publicly traded firms benefit from a confirmation that P!=NP and are there any that lose (e.g., that were betting that P might == NP).<p>There's gotta be money in this news :-)

I think there might be a way to solve all n-SAT problems (if reformulated using conjunctive normal form) in O(C) best up to worst O(C * N * N) time and O(C * N) space (C = number of AND-clauses, N = number of distinct literals from all clauses). would that still be polynomial and a valid proof or even possible (not a mathematician I am)? on the other hand, proving P = NP would not be wise, morally seen, would it?

Looking at the comments at <a href="https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/" rel="nofollow">https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-...</a> there are many points to clarify. Specially the intuition from statistic physics is not true in other examples and the difference is not clear. So ...

4 possible problems with the proof: <a href="http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/" rel="nofollow">http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof...</a>

This is sad: This result, if correct, is the mathematical result of the century; however, it still hasn't appeared in Google News or Google trends.

* RSA and all our other current crypto algorithms breathe a collective sigh of relief <i>

Wow. 100% of zac’s 724 karma points come from this post &#38; his comments on it.

bñpg en el cual se puede jugar al mitico mario bros.<p><a href="http://blog-de-un-youtube-facebook-tuenti.blogspot.com/" rel="nofollow">http://blog-de-un-youtube-facebook-tuenti.blogspot.com/</a>

Everyone has been suspecting or assuming that P is a strict subset of NP for decades. Still, every time someone proposes a serious attempt at proving it, it's front page news and smart people will have to comb over the argument for months to have confidence that it's right.<p>The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good data set could verify the proof in a few minutes. Just run the proof on a hard 3-SAT or whatever and observe the answer returning significantly before the heat death of the universe.<p>So what we think is true is insanely hard to verify but what we think is false is blazingly obvious to check. Chalk another one up for irony.

See, all these monstrous old companies such as IBM and HP, they hire pure scientists such as Chaitin and this guy, and every once in awhile it pays off. I have feeling, yonger companies, with their own research departments, they are still very down to earth, and look for immediate profit from R&#38;D.

The two main consequences that would follow are (from Wikipedia):<p>"A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place."<p>"Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced."<p>So basically we can focus on finding good approximations to NP problems and feel safe that this proof won't immediately jeopardize all of our bank accounts.

Hee is another PDF: <a href="http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf" rel="nofollow">http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf</a>

What to do? Read paper or hit next months deadline...

P = NP if and only if N = 1 or P = 0

That paper is written just a smidgen above my reading level.

I always felt that it was logical that N != NP. However, I certainly couldn't prove it.

Interesting

Can someone call Knuth? If he gives it the thumbs up then I'll believe it.

Proving P ≠ NP is like finding the Higgs Boson. It doesn't change anything and a lot of people spent a lot of time showing that they have spent a lot of time changing nothing.