[dalton]

WOW.

Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal.

As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof.

Read the "Consequences of Proof" section in the Wikipedia article here: http://en.wikipedia.org/wiki/P_versus_NP_problem

[edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is already sort of assumed.

[tzs]

It seems rather unlikely it would be a hoax. The author has published in this field before, in peer reviewed journals: http://logcom.oxfordjournals.org/cgi/content/abstract/15/5/5... or http://portal.acm.org/citation.cfm?id=1185240

Looking at his page at HP Research, he has several other publications in legitimate areas, and seems to be a well qualified researcher.

He may be wrong in this paper, but there's no reason to suspect its a hoax or that he's some kind of kook (as many other comments have sort of implied).

[ynniv]

a) Complicated academic proofs take (and should take) months if not years to verify, and will only be "front-page news" after verification. This is hardly the first unverified proof of the [edit: possible (in)]equality of P and NP.

b) The practical consequences of P=NP are immense. The practical consequences of P≠NP are that we can stop looking for computational unicorns and fairies.

We have for some time thought that P≠NP, but boy do people like those unicorns and fairies.

[Groxx]

I doubt it'll impact the unicorns-and-fairies searches significantly. Most people already work under the assumption that P≠NP.

Similarly, most people believe the world is round, and we go around the Sun. This hasn't prevented serious flat-Earthers nor geocentrists from existing.

[tel]

It has been something of a damper on their funding, however.

[jacquesm]

> This is hardly the first unverified proof of the equality of P and NP.

in 'a' above didn't you mean to write 'inequality of P and NP' ?

[ynniv]

I meant the general field of equality as it relates to P an NP, but I have edited for clarity.

[macrael]

Well, assuming this proof holds up (and there are already links in the comments to other proofs that P != NP) they have proven what most people already assume, that the two are not equivalent. The consequences of P != NP are mostly just that people can stop spending time looking for ways for P to equal NP. Which is valuable, but doesn't have much "real-world practical usage"

[mjschultz]

Emphasizing the "assuming this isn't a hoax" part, even if it is correct, I don't think it is a life-changing deal.

Computer Scientists have been assuming for years that P does not equal NP, so they've been doing research with that assumption already in place. Proving that the assumption is correct won't hugely change anything.

I'm not trying to knock down the greatness of this proof, but the repercussions aren't going to be that major.

[miloshh]

I do not necessarily agree. There is a large number of open problems in computer science (especially in theory of complexity), and a correct proof of P != NP is very likely to use techniques that will help in resolving the other open problems. The techniques are also likely to change what we're learning in CS courses.