Oh my.Somehow I missed this one from earlier this month. A guy from HP Labs called Vinay Deolalikar claims he has the proof.P %u2260 NP.I’m nowhere near clever enough to follow his arguments (see http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf for a synopsis), but I understand the impact.
If he is right, then in a sense, nothing changes.It’s just that we will now know for sure that there is no magic formula that will revolutionise the efficiency of our software. The proof will confirm what has been long suspected.However, if the proof holds up, then it is a major milestone in computer science.I mean MAJOR.
Nothing personal against Mr Deolalikar, but I really hope the proof does not hold up.The idea that P could just possibly equal NP is so beguiling.
No idea what I am talking about?Here comes Wikipedia to the rescue! http://en.wikipedia.org/wiki/P_%3D_NP_problem
And here is a really easily digestible explanation from the good ol’ BBC.Jigsaws work for me!