Hacker News new | comments | show | ask | jobs | submit login
Scott Aaronson adds $200K to prize money if P≠NP proof correct (scottaaronson.com)
56 points by lkozma 2307 days ago | hide | past | web | 22 comments | favorite

This is a confusing post by Aaronson. A commenter on that post interprets the offer to mean that Aaronson thinks the proof is almost certainly flawed, arguing that if expressing his certitude has a value of (say) $100 to Aaronson, then Aaronson believes the probability that it is correct is 1/2000. I originally read it this way as well, as did Eliezer: http://news.ycombinator.com/item?id=1587295

But then Aaronson responded by saying "If I were a Bayesian rationalist, I’m sure I’d agree with you!" and instead claims that the rationale for the $200k is that "If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it." and that "If P≠NP is proved, then to whatever extent theoretical computer science continues to exist at all, it will have a very different character."

That almost sounds like the justification for a reversed insurance bet, except of course that if the proof if wrong then Aaronson doesn't stand to gain anything. So yeah, confusing.

Bottom line, I would caution against interpreting this to mean Aaronson is betting against the proof.

I think he believes that P!=NP, but he also believes that the proof offered is deeply flawed.

His bet is to emphasize the second point. The fact that he wont' gain anything if the proof is wrong and lost $200K if the proof is correct only underscores how strongly he believes the proof is almost certainly flawed.

Well, he also states that he hasn't really spent any time analyzing the proof, so it's not like he knows that it's deeply flawed. Isn't Aaronson maintaining a bit of a bad-boy online persona? Could just be his way of saying what Bill Gasarch just wrote on his blog:

"So what are my uninformed views? If I was a betting man I would bet that it won't pan out. I would bet that he proved something very interesting, but not P ≠ NP. Why do I think this? This is NOT based on the author who seems to be a person to be taken seriously. Its just that the problem is so hard and we've made no progress on it since... . Hmmm, when is the last time we made progress on it?"

There has been lots of progress. We know a lot of things that (for sure!) that can't settle the question.

To quote (http://news.ycombinator.com/item?id=1586749): >> It's known that a proof resolving P vs NP can't relativize, can't be "natural", and can't "algebrize". <<

Aaronson doesn't stand to gain anything

Well, he does explain what he stands to gain in the post: a clear conscience that he's being fair to Deolalikar whilst not expending any hard work on his proof. He's buying the right to enjoy the rest of his vacation. I think it makes sense. It's easy to see how he would feel both obligated to respond to all the people asking about this and annoyed about it, and this is a clever way out of the dilemma.

Edit: "I wanted to stop having to answer emails about this. To me, that’s easily worth the possibility of paying $200k."

> Edit: "I wanted to stop having to answer emails about this. To me, that’s easily worth the possibility of paying $200k."

I guess a guy may be as outrageous or egomaniac as he wants on his own blog, but how does that make it hacker news, or news at all? I don't care if he's an expert at the subject, there's no content at all about the proof in that post.

Oh, I'd say it's well within the guidelines. Interesting new phenomena are allowed to be frivolous.

I don't see what else it could mean. Why would P!=NP change his life dramatically? Maybe you're thinking of P=NP?

Check his comment to a poster that asked the same thing (why would P != NP change anything):

    P≠NP is exactly the ‘expected’ answer! But proving that
    expected answer has been the central goal of the field 
    for 40 years—not so much (in my opinion) because the 
    answer itself is in serious doubt, as because of how much 
    will need to be learned about computation on the way to 
    the proof. If P≠NP is proved, then to whatever extent 
    theoretical computer science continues to exist at all, 
    it will have a very different character.

I still don't get it. I asked on his blog.

P!=NP is a big deal in computational complexity as

1) It would solve one of the most important problems in computer science and mathematics 2) Understanding of the proof and the methods it uses could very likely lead to solving other problems in computational complexity. 3) Furthermore, the proof would shed light on why certain problems are hard. Such an understanding could lead to better heuristics to solve those problems.

I'm glad you asked, I couldn't figure it out either. I could see P = NP being a big deal, but I thought we'd all been kind of assuming P != NP

@sidww2: Thanks that explains it pretty well. I guess we don't really know why hard problems are hard right now. That sounds important to figure out.

BTW, why can't I respond to sidww2's comment? There's no reply button.

It's the anti-flamewar feature. The deeper the thread, the longer it takes for the reply button to appear.

No one explains it on the blog either. They all think I'm asking about P=NP.

Oh well, maybe this guy's life will change if P!=NP is proven, but the rest of us will carry on normally.

I am not that convinced admittedly. He makes statements like this in his blog :

> I’ll leave it to the commenters to debate whether Deolalikar’s paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong.

I know next to nothing about P!=NP, but am quite familiar with the statistics literature. Glancing at this paper made me immediately skeptical. Pages 12-27 are reviews of very basic results in statistics. Maybe it sounds like important stuff to CS researchers unfamiliar with this research, but to me it sounds like a basic review of results. That violates Scott's Rule 8. It probably also violates Rule 10 as well, but I'm not familiar with what's considered powerful in CS.


I was not really commenting on the paper or its contents. That is beyond me.

Rather I was commenting on the fact that the blog post is not as neutral as some commentators believed it to be.

The proof in questions attempts to show that P != NP, contrary to the title here.

I posted it as P!=NP originally but the editors changed the title (or are exclamation marks removed by default ?)

I think there's a scrub rule about '!' since it's a predictor of a biased headline.

My favorite part of the internet is the potential to archive the trivial. Looking back at history during ground breaking revelations you may be able to find an old news paper that may have published a few of the better written opinions. Today though publishing your thoughts is effortless, and storing data is (relatively) cheap. The potential exists to archive the thoughts, and reactions of common people (as well as experts) which provide a fantastic historical perspective. Something that never existed before. I hope someone out there (like wayback machine) is working on this :)

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact