Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

P ≠ NP

scribd.com

Post reply on HN
Print view View original

21–30 of 233 posts

Re: P ≠ NP

#21

Post by kjrose »

[deleted] wrote: post #17
macrael wrote: post #15

Earlier quoted context omitted.

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]

Yeah, in general it's believed that any proof that P != NP would likely provide a lot of insight into which factors of an NP system make it difficult, and thus potentially allow us to divide even cleaner problems which are "easily" solved and problems which are "difficult to solve."

Re: P ≠ NP

#22

Post by gbhn »

[deleted] wrote: post #17
macrael wrote: post #15

Earlier quoted context omitted.

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]

The huge consequences are if P = NP (which no-one really believes).

Re: P ≠ NP

#23

Post by kjrose »

benhalllondon wrote: post #10

Anyone got a link to any proper discussion?

Yeah, I'd be curious to see what people who are still working in the field have to say. My red flags went up as soon as I read "statistical" in the abstract, since that could easily imply the common problem of assuming the existence of a secure PRNG. However, I haven't read the entire paper in depth (and likely won't have time to anytime soon), so I don't really know if that common trap was fallen into.

Re: P ≠ NP

#24

Post by aswanson »

noahlt wrote: post #12

Why isn't this in a peer-reviewed journal?

Because it hasn't undergone the proper level of review in order to be published in one. As it stands, there is no reason to take it seriously until it has been. There have been several posts of such papers here before, and I would highly advise the level of skepticism expressed by a fellow HNer with submissions like this c.f. : http://news.ycombinator.com/item?id=893877

Re: P ≠ NP

#26

Post by carnevalem »

abstractbill wrote: post #20
[deleted] wrote: post #17

Earlier quoted context omitted.

[deleted]

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.

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?

Re: P ≠ NP

#27

Post by scott_s »

aswanson wrote: post #24
noahlt wrote: post #12

Why isn't this in a peer-reviewed journal?

Because it hasn't undergone the proper level of review in order to be published in one. As it stands, there is no reason to take it seriously until it has been. There have been several posts of such papers here before, and I would highly advise the level of skepticism expressed by a fellow HNer with submissions like this c.f. : http://news.ycombinator.com/item?id=893877

Granted, but this author does not set off any crackpot flags: he's had plenty of prior publications in areas relevant to the proof and works in an industry research lab. Another poster points this out: http://news.ycombinator.com/item?id=1585999

Re: P ≠ NP

#28

Post by tzs »

dalton wrote: post #4

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…

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

Re: P ≠ NP

#29

Post by emmett »

tzs wrote: post #3

102 pages via one of the most annoying PDF readers on the planet? No thanks. There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.

Have you tried Scribd since they've transitioned to HTML 5? I now find it quite usable.

Re: P ≠ NP

#30

Post by ramidarigaz »

carnevalem wrote: post #26
abstractbill wrote: post #20

Earlier quoted context omitted.

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.

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?

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

Post reply on HN