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

121–130 of 233 posts

Re: P ≠ NP

#121

Post by aswanson »

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

Warranted. I just despise hype and sensationalism, particularly those concerning scientific breakthroughs. The title of the submission echoed similar hollow, dramatic claims and triggered my skeptical response.

Re: P ≠ NP

#122

Post by [deleted] »

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

To quote the announcement email which zacs posted earlier: 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. So based off this solitary data point, it seems that while they might hire the brains it doesn't necessarily follow that they have…

[deleted]

Re: P ≠ NP

#125

Post by faboo »

lulin wrote: post #31
carnevalem wrote: post #26

Earlier quoted context omitted.

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.

It isn't actually _necessary_ for a P=NP proof to be constructive. A constructive proof would probably be easier to reason through, but it is prossible to prove the existence of an algorithm without providing one.

Re: P ≠ NP

#126

Post by bdr »

randomwalker wrote: post #41

Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts a…

Another thing. It's known that a proof resolving P vs NP can't relativize, can't be "natural", and can't "algebrize". (See http://portal.acm.org/citation.cfm?id=1490272&dl=GUIDE&#... and its references for what this means.) The paper doesn't directly address how it avoids these barriers. It does mention the first two barriers in passing. Maybe the answer is obvious to anyone who could read this paper.

Re: P ≠ NP

#127

Post by zulfikar_ramzan »

randomwalker wrote: post #41

Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts a…

Regarding your next to last point, it seems like there has been some prior work involving statistical physics techniques in computational complexity theory; see e.g., http://cdsagenda5.ictp.it/full_display.php?ida=a01155.

Re: P ≠ NP

#129

Post by zulfikar_ramzan »

randomwalker wrote: post #41

Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts a…

It seems like there has been some prior work involving statistical physics techniques in computational complexity theory; see e.g., http://cdsagenda5.ictp.it/full_display.php?ida=a01155.

Re: P ≠ NP

#130

Post by akshayubhat »

zacs wrote: post #45
JeanPierre wrote: post #39

Earlier quoted context omitted.

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

As another commenter mentioned, it will likely take months or even years to verify.

not necessarily, PRIMES in P was accepted by the community in few weeks.
Post reply on HN