Several points on the question of whether the proof is likely to be correct:
* 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 was circulated and someone other than the author made it public.)
* Therefore a proper assessment is going to take a while. Until then we can only speculate :-)
* 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.
* 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.
* 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.
* 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 (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry.
* 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 http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)
* 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.
* 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.
* 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.
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.
* 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.
Well, Wiles didn't publish intermediate results either, partly because someone might have beat him to the final result with those intermediate results. It would also give away what he was working on. Deolalikar was aiming for the grand prize as well, so skipping the publishing of intermediate results doesn't seem strange to me.
The conclusion might seem to be that prizes harm science.
Which sucks, but intermediate results are important for science as a whole; if there's significant financial reason to withhold them, we're no better than the alchemists.
Agree fully. Also worth considering if this proof turns out to be correct, is that he will probably have employment contracts and speaker deals dwarfing that $1M quite soon.
You can't eat prestige. Nor find joy in a life of isolation. Look at Rembrandt's philosopher if you want the true picture of the life of the mind.
How history remembers you only matters after you're dead. Can you really tell someone to live a life of solitary confinement? The isolating parts of academia honestly suck. But everyone convinces themselves that academia is so great, in part because so many have gone before, suffering, down the same path.
Look at all the theoretical physicists and mathematicians. Do you think these people are HAPPY? Remember, if you leave math you are "dead." It's about sacrifice, not about your health or happiness as a human being.
The best part of academia is the collaboration, the social aspects. As for the environment, it could definitely be renovated to make accommodation for humanity. Obviously that will never happen. So there needs to be big CAUTION signs posted up whenever someone lauds the greatness of academia, saying it is not all fun and games, lots of people spend decades locked in offices hunched over pieces of paper.
I don't think academia is really like that. One of my former roommates was a Physics PhD student at MIT, so I know him and his colleagues. They all drank beer and played chess and cards in this one basement bar in Cambridge, did stuff like hang gliding, rock climbing, ultimate frisbee and played in various awful experimental-folk bands. They were nerds but they were all bros and even attracted the weird kind of cyber-hippy chicks who are into dudes like that. They all eventually got married. They seemed pretty happy to me. In contrast I once got stuck in a corporate programming job, which was the most uninteresting and socially isolating experience of my entire life.
Whenever I read these HN screeds against academia, I wonder what they are comparing it against. In my experience academia was way more interesting and fun than working as a professional programmer. The only thing good about the later is that it pays a lot.
Well maybe those physics PhDs are a lot better at socializing than me. I remember spending years of my PhD trying to make friends, going to bars/rock climbing/dances/running clubs etc to try and meet friends, but never got any where, and just feel this crushing depression every day I have to go to work and sit down at a computer for 8 hours. I feel roughly the same in a corporate or academic environment, it's the result of so much being by oneself. Perhaps I shouldn't have gone into computers?
However, Academia for the most part I think is just that sort of environment, I have commiserated with numerous PhD students who say the same thing. If one is into computers, both academia and computer engineering as career tracks are rather isolating, but some seem to like it, vs some get lonely, perhaps it's something psychological, and I'm not really intended to be such an introvert. Who knows.
I don't think academia is a bad career as long as one can get tenure at a good school, or in a good industry lab, so as to work with good people. I guess whether one can take it psychologically just depends on the individual.
Although I do agree that maybe if one had kids+wife or worked hard to be social, the 8 hours of isolation a day wouldn't be that bad. It might even be relaxing! So maybe professor is a good job for one in old age. But still I would worry about causing my students to suffer through isolation.
Actually sorry for my complaints. I thought about this more and realized being a professor is actually pretty good socially. I think being a grad student is just hard, unless you are very outgoing, and can get out of the lab.
I guess I just wanted to caution people that a career in computers and/or academia can very isolating unless one picks the right path. Moderation in all things.
First, Well the guy in question works in R&D lab of HP, and must be getting paid at least 120k$ per year. He also seems to have a good family and thus a social life :D
I fail to understand why you draw such a poor picture of a Maths / Physics PhD's life. Professors have a lot of interaction with students thus it is not exactly solitary confinement. Your picture of Academia is too dark.
I agree that there are people who get stuck in doing one Post-Doc after other and never get any tenure in life, surely it sucks for them but there are several Physicists and Mathematics PhD students who end up as a Quants on Wall Street and earn huge money.
If you read any posts / articles written by professors advising aspiring PhD students, you would rarely find them portraying a PhD life as fantasy filled life. So in my opinion Caution signs are already there.
Though I was just reading the synopsis, and the statistical physics part seems to be proven: "The 1RSB ansatz of statistical mechanics says that the space of solutions of random k-SAT shatters into exponentially many clusters of solutions when the clause density is sufficiently high. This phase is called 1dRSB (1- Step Dynamic Replica Symmetry Breaking) and was conjectured by physicists as part of the 1RSB ansatz. It has since been rigorously proved for high values of k. It demonstrates the properties of high correlation between large sets of variables that we will need."
Another thing. It's known that a proof resolving P vs NP can't relativize, can't be "natural", and can't "algebrize". (See http://portal.acm.org/citation.cfm?id=1490272&dl=GUIDE&#... and its references for what this means.) The paper doesn't directly address how it avoids these barriers. It does mention the first two barriers in passing. Maybe the answer is obvious to anyone who could read this paper.
In a cursory reading, I think I can address these criticisms. Although one would have liked the author to call out each in his introduction.
Naturalization: This proof is not combinatorial, it is based on a model of formal logic. This is addressed by the author directly.
Relativization: This is proof by contradiction and relies on understanding the solution space of k-SAT instances, not on diagonalization.
Algebrization: This proof looks beyond the size of small circuit into how the circuit inputs interact and how this interaction spreads throughout the circuit.
Thanks. I think you nailed just about every one of my concerns about this paper. I've only read the introduction, but if the rest of the paper can deliver what the first 16 pages promise, it looks like a winner to me. I suspect that if there's some problem hidden somewhere, it's a case of showing that some property or another of k-SAT holds almost always in the limit, but not being able to show that any specific instance of k-SAT has that property. And, if that's the case, it's probably a symptom of relying on one of those physics "theorems" you've mentioned. Color me cautiously optimistic, here.
Regarding your next to last point, it seems like there has been some prior work involving statistical physics techniques in computational complexity theory; see e.g., http://cdsagenda5.ictp.it/full_display.php?ida=a01155.
I'm not sure if it is or isn't weird that he hasn't published on complexity theory. I recall Gasarch publishing a poll in SIGACT where a handful of the researchers polled claimed that it'll be resolved by someone outside of the field.
Regardless, from reading the synopsis of the proof, I'm skeptical to the point of disinterest.
Why are you skeptical of the proof to "the point of disinterest"? I would assume that a researcher with HP with a dual Ph.D.s from USC wouldn't haphazardly make such a claim.
* 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 was circulated and someone other than the author made it public.)
* Therefore a proper assessment is going to take a while. Until then we can only speculate :-)
* While the crank attempts at P =? NP are statistically much more common (http://news.ycombinator.com/item?id=347295), this isn't one of them. The author is a legit computer scientist: http://www.hpl.hp.com/personal/Vinay_Deolalikar/
* 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.
* 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.
* 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.
* 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 (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry.
* 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 http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)
* 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.
* 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.
* 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.
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.