5 ms·

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 t

by dalton 16y ago

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

mjschultz 16y ago
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 16y ago
  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.
macrael 16y ago
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"
- deleted 16y ago
  [deleted]
  - abstractbill 16y ago
    A proof of P = NP would have huge practical consequences. A proof that P != NP "only" represents a huge advance in the theory of computation.
    - carnevalem 16y ago
      I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it. Could you explain what some of those consequences be? Does P = NP really need to be proved to achieve those practical consequences? Can't it just be assumed to be true and then see what the result is?
      - ramidarigaz 16y ago
        If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions. Wikipedia should answer most of your questions regarding the consequences: http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof
        nkassis 16y ago
        To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial). NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).
        jules 16y ago
        Not true. A polynomial time algorithm for NP complete programs is known (if P=NP that is). You just need to prove P=NP to prove that it is polynomial time. http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-...
ynniv 16y ago
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.
- jacquesm 16y ago
  > 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 16y ago
    I meant the general field of equality as it relates to P an NP, but I have edited for clarity.
- Groxx 16y ago
  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 16y ago
    It has been something of a damper on their funding, however.
tzs 16y ago
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/577 http://logcom.oxfordjournals.org/cgi/content/abstract/15/5/5... or http://portal.acm.org/citation.cfm?id=1185240 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).

by dalton 16y ago

mjschultz 16y ago

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 16y ago
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.

macrael 16y ago

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"

deleted 16y ago
[deleted]
- abstractbill 16y ago
  A proof of P = NP would have huge practical consequences. A proof that P != NP "only" represents a huge advance in the theory of computation.
  - carnevalem 16y ago
    I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it. Could you explain what some of those consequences be? Does P = NP really need to be proved to achieve those practical consequences? Can't it just be assumed to be true and then see what the result is?
    - ramidarigaz 16y ago
      If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions. Wikipedia should answer most of your questions regarding the consequences: http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof
      - nkassis 16y ago
        To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial). NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).
      - jules 16y ago
        Not true. A polynomial time algorithm for NP complete programs is known (if P=NP that is). You just need to prove P=NP to prove that it is polynomial time. http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-...

ynniv 16y ago

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.

jacquesm 16y ago
> 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 16y ago
  I meant the general field of equality as it relates to P an NP, but I have edited for clarity.
Groxx 16y ago
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 16y ago
  It has been something of a damper on their funding, however.

tzs 16y ago

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/577 http://logcom.oxfordjournals.org/cgi/content/abstract/15/5/5... or http://portal.acm.org/citation.cfm?id=1185240 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).