* 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.
* 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.
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.
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.
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.
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.
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.
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."
I did not dig into the references yet, though.
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.
Regardless, from reading the synopsis of the proof, I'm skeptical to the point of disinterest.
(I apologize for not providing a link -- but the only URL I was able to find from Google: http://www.cs.umd.edu/~gasarch/papers/poll.pdf is broken.)