The hardest question in Computer Science

Since Comp Sci only got two mentions in the Top 125 science challenges, it was interesting to see that someone had come up with another proof for one of them - that P = NP. My maths is a little rusty so unfortunately wasn't able to fully to proof in full (shame on me), but its re-assuring that it's already been listed on the P-versus-NP page. Possible we have a way to go before we get a proof.

The great thing about the article though was that it led me to this article [PS file] by William Gasarch which surveys opinions of the great and the good in mathematics on when and how the question might be solved. Choice quotes (!):

• Richard Chang (Univ of MD Balt. County, 2066, P != NP) In the year, 2066, the idea that computers will double in speed every 18 months (Moore's Law) has been ludicrous for 50 years. As such, no one uses asymptotic analysis anymore. Programs are written in assembly language to shave the running time. Some poor assistant professor will prove that P != NP and fail to get tenure for it.


• Stuart Kertz (University of Chicago, 2050, P != NP) Knowing Ketan Mulmuly, I live in fear that the slution will be via algebraic geometry, and it will come soon enough that I'll be expected to understand it. An alternative nightmare is that the undergraduate who solves it will publish his solution in French.


• Ming Li (Waterloo, P != NP) For God's sake, let's keep it open for another 100 years! NSF needs to be convinced that theoretical CS is still relevant and supports it.
  

But there are plenty of less tounge in cheek answers too - well worth a read.

UPDATE: A nice explanation of the problem by Craig Feinstein.