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

71–80 of 233 posts

Re: P ≠ NP

#71

Post by mquander »

endlessvoid94 wrote: post #51
wingo wrote: post #36

Earlier quoted context omitted.

This is not the point.

Sure it is. Scribd has succeeded in going from "the worst pdf viewer on the web" to something that's perfectly usable using HTML5.

Perfectly usable compared to what?

A big toolbar at the top, a big toolbar at the bottom, a big sidebar, none of which have any information I want to see; ads all over, and I have to sign up for their website to download the PDF.

That's not even as good as Acrobat (last I used it), never mind a lightweight PDF reader, never mind Chrome's integrated PDF rendering.

Re: P ≠ NP

#72

Post by acangiano »

leif wrote: post #68
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…

Somewhere, deep in a dark corner of my heart, I hope and pray that this paper is correct, just so we can keep and revere the immortal words "I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts ."

The font was specified to indicate that this proof, indeed, fits into the margin.

Re: P ≠ NP

#74

Post by jacoblyles »

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.

Re: P ≠ NP

#75

Post by pmiller2 »

scott_s wrote: post #27
aswanson wrote: post #24

Earlier quoted context omitted.

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

Also, the paper was written using LaTeX. I have a friend who spent a semester helping to edit a small mathematics journal, and, with virtually 100% accuracy, you could tell the crackpot papers from the serious ones based simply on whether they used LaTeX or not.

Re: P ≠ NP

#76

Post by alextgordon »

amvp wrote: post #38
emmett wrote: post #29

Earlier quoted context omitted.

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?

It seems they're A/B testing it. I got the html5 viewer all but one time viewing this.

Re: P ≠ NP

#78

Post by RiderOfGiraffes »

Ramfjord wrote: post #65
WildUtah wrote: post #54

Everyone has been suspecting or assuming that P is a strict subset of NP for decades. Still, every time someone proposes a serious attempt at proving it, it's front page news and smart people will have to comb over the argument for months to have confidence that it's right. The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good da…

P is a strict subset of NP. If you can solve the problem in polynomial time, then you can verify a solution simply by generating it.

That means it's a subset and is trivial. To claim it's a strict subset means there's something in NP that's not in P.

Re: P ≠ NP

#79

Post by mkramlich »

leif wrote: post #68
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…

Somewhere, deep in a dark corner of my heart, I hope and pray that this paper is correct, just so we can keep and revere the immortal words "I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts ."

If he can also prove it in 7pt font THEN I'll be impressed. Until then, meh.

Re: P ≠ NP

#80

Post by dasht »

shrikant wrote: post #73
dasht wrote: post #56

So: What publicly traded firms benefit from a confirmation that P!=NP and are there any that lose (e.g., that were betting that P might == NP). There's gotta be money in this news :-)

There sure is: http://www.claymath.org/millennium/P_vs_NP/

Ah, yes. No, I meant for the outside investor with early news of the purported proof who is willing to bet that it holds up.

For example, if there is some crypto company whose business is premised on hedging that a "P == NP" proof is just around the corner - short them. Alternatively, maybe buy the firm we think of as RSA. That kind of thing.

This paper hasn't yet got a lot of press attention and I'm only about 1/4 joking when I say I'm curious as to what effect it will have on various stocks if it isn't quickly debunked.

Post reply on HN