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

291–300 of 303 posts

Re: A Solution of the P versus NP Problem?

#291

Post by mathperson »

eatplayrove wrote: post #251
mathperson wrote: post #152

1. no google scholar account 2. three publications on the arxiv. I am willing to toss this out of hand...but look at yitang zhang or perelman. who knows? best of luck

although not prolific, the guy has published in top cs theory conferences and journals: http://dblp.uni-trier.de/pers/hd/b/Blum:Norbert dblp is the proper place to check computer scientists' record, not arxiv/google scholar.

I am not really sure I agree. At least in my part of CS in the united states arxiv/google scholar are pretty omnipresent. Thank you for pointing me towards a new resource.

Re: A Solution of the P versus NP Problem?

#292

Post by kbutler »

pedrocr wrote: post #260
kbutler wrote: post #134

Earlier quoted context omitted.

No, but this one was.

Could you clarify what was needlessly political? I can't seem to find anything political there at all.

Injecting a controversial (and mostly detested here) political figure into an unrelated topic.

Re: A Solution of the P versus NP Problem?

#293

Post by ndl »

ethan_g wrote: post #83

Interesting that this is the second P!=NP proof from a University of Bonn researcher. Other one, by Mathias Hauptmann, is here: https://arxiv.org/abs/1602.04781 I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed. I might not get too excited over this proof, eithe…

Also interesting: if you look at the acknowledgements of Hauptmann's paper (at the end, just before references), he says, "I would like to thank Norbert Blum for carefully reading preliminary versions of the paper, for helpful remarks and discussions, for his guidance and patience and for being my mentor." This means Blum knew about this past attempt and presumably thought it correct enough to put on arXiv. I assume from the current paper that he has changed his mind since then.

Re: A Solution of the P versus NP Problem?

#294

Post by kbutler »

monochromatic wrote: post #290
vecter wrote: post #252

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Virtue_signalling Virtue signalling is the conspicuous expression of moral values done primarily with the intent of enhancing standing within a social group. I don't think Aaronson states his views on Trump with the hopes of increasing his social status. He does it because it's just what he feels and wants to express himself.

And which part of that definition has anything to do with the views being inauthentic? I feel like I'm taking crazy pills here.

You're correct.

Virtue signalling is usually done by people who sincerely believe the values they espouse - but they emphasize or show those values in order to gain or reinforce social status within the group. It usually is done by proclaiming things you hate, rather than things you like.

If the comment adds nothing besides an "I'm with you guys, that's the worst", it's fair to see and describe it as virtue signalling.

And yes, it happens on both sides of the aisle - heard lots of conservatives proclaiming their distaste for Obama over the last decade.

Re: A Solution of the P versus NP Problem?

#295

Post by kybernetikos »

monochromatic wrote: post #290
vecter wrote: post #252

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Virtue_signalling Virtue signalling is the conspicuous expression of moral values done primarily with the intent of enhancing standing within a social group. I don't think Aaronson states his views on Trump with the hopes of increasing his social status. He does it because it's just what he feels and wants to express himself.

And which part of that definition has anything to do with the views being inauthentic? I feel like I'm taking crazy pills here.

When you express a view that you don't hold in order to receive social approval, or when you express a view that you hold lightly with more intensity and frequency than you would except for your desire to receive social approval you are being inauthentic.

The whole value of the phrase 'virtue signalling' is that it accuses those you disagree with of inauthenticity. If I'm saying a thing I genuinely believe because I genuinely believe it, I'm not virtue signalling. It's only if the reason for saying the thing is to gain social approval that it's 'virtue signalling'. Any assumption that your opponent is doing something for this reason is uncharitable, and kills rational debate. It's essentially an ad hominem attack.

It's also ignoring the fairly detailed entry that Scott posted explaining in his own words why he started talking about Trump in his blog: http://www.scottaaronson.com/blog/?p=2777 when previously he'd avoided the subject.

Maybe it is virtue signalling, or maybe he really did feel as he claimed, that he had a moral responsibility to speak out against Trump. If you assume that it is only 'virtue signalling', you are cutting yourself off from engaging with his points.

Re: A Solution of the P versus NP Problem?

#296

Post by pedrocr »

kbutler wrote: post #292
pedrocr wrote: post #260

Earlier quoted context omitted.

Could you clarify what was needlessly political? I can't seem to find anything political there at all.

Injecting a controversial (and mostly detested here) political figure into an unrelated topic.

I meant actual examples. But on second read I assume this is about the blog in general and not this post in particular that doesn't seem to have any Trump references.

Re: A Solution of the P versus NP Problem?

#297

Post by Blaisorblade0 »

soberhoff wrote: post #280
fmap wrote: post #273

Earlier quoted context omitted.

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.

That's only obvious in a vacuous sense.

As a PhD student in Programming Languages, can I request a reference?* Nobody managed to provide one on MathOverflow, and that's the StackExchange for professional mathematicians:

https://mathoverflow.net/q/226966/36016

Of course, your claim is vacuously true, since you can add a trace of all steps of a proof verifier. It's also vacuously true because you can add a dump of the Internet to the proof. Neither thing is insightful.

> what we normally think of as an "honest proof" is a series of steps each of which follows from the previous by application of one of a finite number of axioms or rules of deduction, and such an "honest" proof is thus checkable in linear time by checking each step

Also, for the record: actual formal proofs for (say) standard ZFC are exponentially bigger than anything you want to work with.

EDIT: To clarify, I didn't mean to imply I'm some authority, just to suggest I'm not so obviously* an idiot. Which was maybe stupid anyway.

Re: A Solution of the P versus NP Problem?

#298

Post by soberhoff »

Blaisorblade0 wrote: post #297
soberhoff wrote: post #280

Earlier quoted context omitted.

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.

That's only obvious in a vacuous sense. As a PhD student in Programming Languages, can I request a reference?* Nobody managed to provide one on MathOverflow, and that's the StackExchange for professional mathematicians: https://mathoverflow.net/q/226966/36016 Of course, your claim is vacuously true, since you can add a trace of all steps of a proof verifier. It's also vacuously true because you can add a dump of the…

Well, I've spent a lot of time with theorem provers as well as with normal mathematics. I've never experienced an exponential blowup when formalizing mathematical ideas. It would always boild down to step-by-step verification. And I don't see any reason to suspect that the paper under discussion uses non-standard techniques.

Re: A Solution of the P versus NP Problem?

#299

Post by Blaisorblade0 »

davesque wrote: post #186
WhitneyLand wrote: post #72

Earlier quoted context omitted.

It shouldn't be career ending unless there's been malfeasance or some kind of sloppy work. The people who go down hard usually have some crime beyond audacity. It could easily cause some painful embarrassment, but hopefully that would pass with time. Maybe embarrassment similar to that faced by researchers who's results suggested FTL communication, but it turned out to be a bad fiber-optic cable. I didn't follow up b…

Agreed. Even in the event of the discovery of work which would qualify as minimally sloppy, I'd think his reputation (if not wanting of some polish) would still be intact after a quick retraction.

I mostly agree but there is a small effect: "Claims spectacular proofs with flawed arguments" might still be reason to doubt his future proofs more until verified. And mathematicians do use such criterions before reading unverified claimed proofs of hundreds of pages (not uncommon). And since some proofs target tens or hundreds of persons, that can be a problem. I've read such stories, though I don't have a reference at hand.

Re: A Solution of the P versus NP Problem?

#300

Post by evincarofautumn »

soberhoff wrote: post #298
Blaisorblade0 wrote: post #297

Earlier quoted context omitted.

That's only obvious in a vacuous sense. As a PhD student in Programming Languages, can I request a reference?* Nobody managed to provide one on MathOverflow, and that's the StackExchange for professional mathematicians: https://mathoverflow.net/q/226966/36016 Of course, your claim is vacuously true, since you can add a trace of all steps of a proof verifier. It's also vacuously true because you can add a dump of the…

Well, I've spent a lot of time with theorem provers as well as with normal mathematics. I've never experienced an exponential blowup when formalizing mathematical ideas. It would always boild down to step-by-step verification. And I don't see any reason to suspect that the paper under discussion uses non-standard techniques.

Wow, this got more replies than I expected. I was partly kidding, in that I don’t think it’s a huge concern for humans, but for example the tableau decision procedure[1] for modal logics such as epistemic logic is EXPTIME-complete[2].

[1]: https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

[2]: https://arxiv.org/abs/0808.4133

Post reply on HN