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

31–40 of 233 posts

Re: P ≠ NP

#31

Post by lulin »

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 I remember correctly, any proof of P = NP would be have to be constructive, so it would immediately give us a fast algorithm for ALL NP-complete problems, as they can all be reduced to each other.

Re: P ≠ NP

#32

Post by miloshh »

mjschultz wrote: post #14
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…

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 goi…

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.

Re: P ≠ NP

#33

Post by abstractbill »

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?

Intuitively:

NP questions take a long time to answer.

P questions take much less time.

The statement "P = NP" means that any NP question can be transformed into a P question. Answering the P question gives you an answer to the NP question.

So, if P = NP, then we can answer questions that we thought were slow, much more quickly than we would have thought possible.

Proving P = NP would (presumably) give you that method for transforming NP problems into P problems. So you would suddenly be able to figure things out easily that currently are hard and take a lot of computing power.

It's often assumed that P = NP would make cryptographic problems much easier to break, but apparently that's not really the case: http://world.std.com/~reinhold/p=np.txt

Re: P ≠ NP

#34

Post by ilkhd2 »

See, all these monstrous old companies such as IBM and HP, they hire pure scientists such as Chaitin and this guy, and every once in awhile it pays off. I have feeling, yonger companies, with their own research departments, they are still very down to earth, and look for immediate profit from R&D.

Re: P ≠ NP

#36

Post by wingo »

emmett wrote: post #29
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.

This is not the point.

Re: P ≠ NP

#37

Post by zacs »

The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail:

Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP

Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highly welcomed.

Sincerely,

Vinay Deolalikar Principal Research Scientist HP Labs

http://www.hpl.hp.com/personal/Vinay_Deolalikar/

Re: P ≠ NP

#38

Post by amvp »

emmett wrote: post #29
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.

I got their flash viewer for this. I do sometimes get the html5 viewer, and I assumed the selection was based on a preference set by the uploader. Isn't it?

Re: P ≠ NP

#39

Post by JeanPierre »

zacs wrote: post #37

The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail: Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts. The proof required the piecing together of principl…

If this proof is up for review, that would mean there could be errors in it, right?

Re: P ≠ NP

#40

Post by lkozma »

I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof):

"The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound."

How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?

Post reply on HN