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

A Solution of the P versus NP Problem?

arxiv.org

Post reply on HN
Print view View original

271–280 of 303 posts

Re: A Solution of the P versus NP Problem?

#271

Post by IronSean »

Myrmornis wrote: post #250
liberte82 wrote: post #158

Earlier quoted context omitted.

North American here, we hear enough Brits speak to get the expression :)

"serious bollocks" means "very questionable statement" in the British English I'm familiar with. Perhaps GP's idiom is from elsewhere. If the reference is to bravery/daring one would use "balls" as in US English, I believe.

"Bollocks" in Britain and "Balls" in North America both refer to the Testes, as does "cojones". So all three statements are actually the exact same slang in regional dialects.

Bollocks, like many slang words, have multiple meanings in different contexts. It can be used as you stated as well, but "What you said is bollocks" and "You have bollocks for saying it" are very different statements.

Re: A Solution of the P versus NP Problem?

#272

Post by sulam »

kevinnk wrote: post #196
nieve wrote: post #116

Earlier quoted context omitted.

I wouldn't be surprised if they gained a bit of respect. If I recall correctly they did everything right - they had an apparently impossible result, they spent a lot of time trying to disprove it, and when they announced they made it clear that they doubted the result. Hiding it because they were sure it was false, but couldn't disprove would have been poor science. It had to be pretty scary to make that announcement…

Actually, there was a bunch of blow back and the main researchers behind the result stepped down. https://www.newscientist.com/article/dn21656-leaders-of-cont...

Reading that, it seems more like they went back to doing research full time instead of being part time administrators -- and probably happier for it.

Re: A Solution of the P versus NP Problem?

#273

Post by fmap »

soberhoff wrote: post #261
evincarofautumn wrote: post #199

Earlier quoted context omitted.

Checking a proof isn’t necessarily easy , of course, in the sense of both human hardness—such as requiring a lot of background, using dense notation, or being very long—and computational hardness, such as using a logic whose decision procedure takes exponential time.

What kind of esoteric logic yields proofs that require exponential time to check?

Proof checking in dependent type theory is nonelementary. Of course, this is a completely artificial result with no real world consequences, but that's complexity theory for you...

Re: A Solution of the P versus NP Problem?

#274

Post by kwaugh »

Tomte wrote: post #39

Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304

Aarsonson has since commented on this paper on his website. He still believes that it's a bogus proof.

Re: A Solution of the P versus NP Problem?

#275

Post by efm »

tl;dr Not crackpot, not proven, interesting math. There's a discussion on Google+ started by John Baez, which includes a comment by Gowers: https://plus.google.com/+johncbaez999/posts/hGshTfdimpZ

There's some interesting ideas in the paper, the researcher has done good work in this area before.

Re: A Solution of the P versus NP Problem?

#276

Post by fazkan »

CarolineW wrote: post #259
fazkan wrote: post #258

As someone with an undergrad level knowledge of the problem can someone please outline the importance of this research. Is this research done in some bounded domain. From what I have read in the comments, there seems to be other papers which have also proved P!=NP. So what does this research add...Just curious, feel free to ignore this...

> From what I have read in the comments, there seems to be other papers which have also proved P!=NP. None of those papers have been accepted as correct, the problem remains open. There's a gazillion articles describing the context and importance, and I suggest you do a web search for something like "P vs NP and why it's important". Here's one: http://www.scottaaronson.com/blog/?p=459 HN discussion: https://news.ycom…

Thanks for the reply. Thats a great article. I have read a lot of articles like that, in fact was planning to write one myself. Just wanted to know more about the paper submitted i.e. what it proposes and the methodology adapted. I tried reading it but couldnt parse the data with all the jargons.

Re: A Solution of the P versus NP Problem?

#277

Post by efm »

choxi wrote: post #14

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.

_The Golden Ticket_ is a non-technical book discussing the implications of solving P vs NP

http://goldenticket.fortnow.com/

Re: A Solution of the P versus NP Problem?

#278

Post by manyoso »

GenerocUsername wrote: post #147
jl6 wrote: post #101

Earlier quoted context omitted.

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

If only we had a way to make finding the flaw as easy as verifying the flaw

My favorite comment. By far.

Re: A Solution of the P versus NP Problem?

#279

Post by interstitial »

1ris wrote: post #146
__s wrote: post #138

Earlier quoted context omitted.

Hence why Scott explicitly takes time to address that there will surely be outliers on both ends

I just wanted to point out that's is not a theoretical possibility, but actual ground breaking work did look sketchy as hell. The "The nice thing about math is that sooner or later the truth comes out" bothers me. The knowlege in Archimedes palimpsest was lost so long the eventually doesn't seem to be much comfort.

When we trust Academia to write their own history books, the theme is always "sooner or later the truth comes out."

Re: A Solution of the P versus NP Problem?

#280

Post by soberhoff »

fmap wrote: post #273
soberhoff wrote: post #261

Earlier quoted context omitted.

What kind of esoteric logic yields proofs that require exponential time to check?

Proof checking in dependent type theory is nonelementary. Of course, this is a completely artificial result with no real world consequences, but that's complexity theory for you...

Well, I'm sure we can all agree that the mathematical paper we're discussing could be formalized into a proof that could be checked in linear time.
Post reply on HN