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

141–150 of 233 posts

Re: P ≠ NP

#141

Post by dmoney »

ilkhd2 wrote: post #34

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.

I don't know if "paid off" is the right word. If P were equal to NP, HP would probably benefit from finding out first. Assuming this is correct, though, all they get is the satisfaction of having hired the guy who happened to discover the proof in his spare time.

Re: P ≠ NP

#142

Post by brg »

lkozma wrote: post #40

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

In regards to mathematics, creativity is displayed foremost in finding connections between different notions and finding logical arguments to support a claim. Mathematical discovery is not in the claim, but in the construction of the proof of the claim.

Mathematical statements are generally easy to state. If P=NP were true, then a valid proof could automatically and efficiently discovered. This would be a kind of creativity automated by technology.

Re: P ≠ NP

#144

Post by nandemo »

jacoblyles wrote: post #74
lkozma wrote: post #40

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

I didn't follow everything in my complexity class, but I believe that P=NP implies that search is as easy as decision. So producing a piece of good music is as easy (up to a polynomial) as deciding if a piece of music is good. If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.

Up to a polynomial.

What if the polynomial is of order 1000 or higher?

I understand asymptotics and the convention that polynomial algorithms are "efficient". However, it might turn out that P=NP but the polynomial is so big that the found algorithm is impractical for normal sized instances.

Re: P ≠ NP

#145

Post by fmora »

xsmasher wrote: post #108
pclark wrote: post #88

Earlier quoted context omitted.

I'm not academic - can you explain why he mentioned the font sizes? Why are they relevant?

I find the sentence comical in its humility and practicality; I assume leif did too. Acangiano puts it in the same league as Fermat's famous note in the margin of his copy of Arithmetica. I assume he included the paper in two font sizes to suit the reader's preference; no deeper meaning.

True, some of those intellectuals must have poor eyesight due to a lifetime of reading.

Re: P ≠ NP

#146

Post by fmora »

dasht wrote: post #53
lkozma wrote: post #40

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

You must read it in context. What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated. You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack. I believe the intent regarding human creativity is that humans ofte…

Lets assume that P==NP, why assume that we would be able to find algorithms to easily crack crypto?

Let me put it another way, lets say that we finally discover that it is possible to time travel to the past. However, the energy needed to travel back int time is the equivalent of a million Suns because that is the amount of energy needed to warp space enough so that time will reverse itself. And we found proof of this when we observed the black holes of two galaxies colliding. So, even if it were possible it would still not matter. Practically speaking, it would still not be possible to travel back in time.

My gut feeling is that if it were to turn out that P==NP that would not necessarily mean that all of a sudden we would be able to find the exact algorithms that make it easy to crack cryptography algorithms easily.

Re: P ≠ NP

#147

Post by Jun8 »

This is sad: This result, if correct, is the mathematical result of the century; however, it still hasn't appeared in Google News or Google trends.

Re: P ≠ NP

#148

Post by leif »

xsmasher wrote: post #108
pclark wrote: post #88

Earlier quoted context omitted.

I'm not academic - can you explain why he mentioned the font sizes? Why are they relevant?

I find the sentence comical in its humility and practicality; I assume leif did too. Acangiano puts it in the same league as Fermat's famous note in the margin of his copy of Arithmetica. I assume he included the paper in two font sizes to suit the reader's preference; no deeper meaning.

Yeah, basically I found it funny juxtaposing the announcement of such a magnificent result (should it end up proving true) with such a mundane, utilitarian comment.

Re: P ≠ NP

#149

Post by rmathew »

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

http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf

The author's page (http://www.hpl.hp.com/personal/Vinay_Deolalikar/) has now been updated to include a direct link to the PDF version (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_p...). He also notes: "The preliminary version made it to the web without my knowledge. Please note that the final version of the paper is under preparation, and is to be posted here shortly (in about a week). Stay tuned."

Re: P ≠ NP

#150

Post by crizCraig »

The two main consequences that would follow are (from Wikipedia):

"A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place."

"Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced."

So basically we can focus on finding good approximations to NP problems and feel safe that this proof won't immediately jeopardize all of our bank accounts.

Post reply on HN