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

261–270 of 303 posts

Re: A Solution of the P versus NP Problem?

#261

Post by soberhoff »

evincarofautumn wrote: post #199
soberhoff wrote: post #177

Earlier quoted context omitted.

Finding flaws in proofs is as easy as verifying them. After all, finding a flaw amounts to just checking a proof. Finding a proof is the truly hard challenge.

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?

Re: A Solution of the P versus NP Problem?

#262

Post by wolfgke »

StavrosK wrote: post #150
mmarx wrote: post #100

Earlier quoted context omitted.

> A career-ending disaster He is a tenured professor in Germany, there is very little that could end his career (essentially refusing to honour his teaching obligations or being convicted of a felony). At worst, this will be immensely embarrassing, but you can't kick professors out just because they make a fool of themselves.

And professors don't just make a fool of themselves because one of their papers had a flaw in it.

You have no idea...

Re: A Solution of the P versus NP Problem?

#264

Post by elnygren »

letitgo12345 wrote: post #263

Some informed discussion -- https://www.facebook.com/shachar.lovett/posts/10155282027901...

There's really nothing there - 11 likes and 1 comment ?

Also, this very same Facebook link was linked to at https://cstheory.stackexchange.com/questions/38803/is-norber... by https://cstheory.stackexchange.com/users/24/opt

Neither this HN user, that FB user nor that stackexchange user seems like anyone important, respected or relevant in the field of CS of this article (correct me if I'm wrong).

Smells like a bad attempt at karma whoring to me.

Re: A Solution of the P versus NP Problem?

#265

Post by taneq »

bradleyjg wrote: post #178
monochromatic wrote: post #136

Earlier quoted context omitted.

Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.

>virtue signaling You know that was an interesting and useful concept before you guys decided to turn into yet another empty insult to fling at people.

It's still an interesting and useful concept even if it's also used as an insult. (Much like you might refer to a colleague's tight new shirt and gold chain as a "mating display" without disparaging biologists' use of the term.)

Re: A Solution of the P versus NP Problem?

#267

Post by kurtisc »

Radle wrote: post #254
jjgreen wrote: post #2

I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.

If you think this is career ending you probably have no idea on how hiring and promoting decisions are made in German universities.

Please can you enlighten me?

Re: A Solution of the P versus NP Problem?

#268

Post by letitgo12345 »

elnygren wrote: post #264
letitgo12345 wrote: post #263

Some informed discussion -- https://www.facebook.com/shachar.lovett/posts/10155282027901...

There's really nothing there - 11 likes and 1 comment ? Also, this very same Facebook link was linked to at https://cstheory.stackexchange.com/questions/38803/is-norber... by https://cstheory.stackexchange.com/users/24/opt Neither this HN user, that FB user nor that stackexchange user seems like anyone important, respected or relevant in the field of CS of this article (correct me if I'm wrong). Smells like a bad att…

That 1 comment raises very serious doubts about that paper. The paper is basically assuming that a polynomial time solvable problem takes super-polynomial time. If it's using that fact in an integral manner then that kills the proof. And even if not, just the fact that the paper is making such a basic mistake raises questions as to how solid the rest of the paper is. Also the guy who made the comment (Luca Trevisan) is a very famous researcher in theory/crypto...

Re: A Solution of the P versus NP Problem?

#269

Post by killercup »

sean2 wrote: post #201
nabla9 wrote: post #194

If established researcher in the field makes a breakthrough of this magnitude I would expect rumors to start to circulating first. Showing the draft to few colleagues to see if they can spot mistakes before 'shaking the world' is probably a good idea.

Hmmm, maybe he analyzed the game theory: If he publishes without consulting peers: If his proof is correct, he gets unending fame, millions in prize money. If his proof is laughably flawed, he'll promptly be forgotten as one of the 100s who have been wrong before him. If he consults his peers: If his proof is correct, he may end up sharing credit, maybe they'll even publish his work quietly under their own name while…

Entirely possible: The paper's author has actually given lectures on game theory.

Re: A Solution of the P versus NP Problem?

#270

Post by sova »

dbaupp wrote: post #216
sova wrote: post #213

Earlier quoted context omitted.

So part of the solution set satisfies P=NP and some satisfy P!=NP?

No, some NP-hard problems are outside NP (i.e. harder than NP), while some are inside. The wikipedia article has a good explanation and a good diagram: https://en.wikipedia.org/wiki/NP-hardness

Thanks many for your kind explanation. It makes more sense now. I forgot that important detail that mapping is pretty easy as most involvements reduce to and from 3-SAT
Post reply on HN