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

The problem is, the most important prize (being able to say "I found it first") is unavoidable.

Yeah, that's what I meant with 'the grand prize'. Not the 1 M$ from the Clay institute; that's just topping on the cake.

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.

Money is the last thing to care about if you solve P ?= NP. Humanity will remember you in same league as Turing Pythagoras Gauss and others.

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.

But, there was no prize for solving FLT other than being able to list on one's CV "Proved FLT."

Not that it matters, but there was the Wolfskehl Prize:

http://www.simonsingh.net/Wolfskehl_Prize.html

You wouldnt actually need to put that in your CV

You actually won't need a CV.

That is a more precise statement :)

Very good summary.

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.

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.

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.

(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.)

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.

He has published in the area of complexity theory: http://portal.acm.org/citation.cfm?id=1185240