5 ms·

Scott Aaronson adds $200K to prize money if P≠NP proof correct

56 points by lkozma 16y ago

rndmcnlly0 16y ago
The proof in questions attempts to show that P != NP, contrary to the title here.
- lkozma 16y ago
  I posted it as P!=NP originally but the editors changed the title (or are exclamation marks removed by default ?)
  - lg 16y ago
    I think there's a scrub rule about '!' since it's a predictor of a biased headline.
randomwalker 16y ago
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 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.
- tocomment 16y ago
  I don't see what else it could mean. Why would P!=NP change his life dramatically? Maybe you're thinking of P=NP?
  - j-g-faustus 16y ago
    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.
    - tocomment 16y ago
      I still don't get it. I asked on his blog.
      - tocomment 16y ago
        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.
      - icey 16y ago
        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 16y ago
        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.
clistctrl 16y ago
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 :)
giantfuzzypanda 16y ago
1. Wait until a serious attempt at proving P != NP is posted 2. Write rambling blog post and offer a ridiculous amount of money for something that now is incredibly unlikely 3. Massive page views 4. ??? 5. PROFIT!

56 points by lkozma 16y ago

rndmcnlly0 16y ago

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

lkozma 16y ago
I posted it as P!=NP originally but the editors changed the title (or are exclamation marks removed by default ?)
- lg 16y ago
  I think there's a scrub rule about '!' since it's a predictor of a biased headline.

randomwalker 16y ago

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 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.

tocomment 16y ago
I don't see what else it could mean. Why would P!=NP change his life dramatically? Maybe you're thinking of P=NP?
- j-g-faustus 16y ago
  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.
  - tocomment 16y ago
    I still don't get it. I asked on his blog.
    - tocomment 16y ago
      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.
    - icey 16y ago
      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 16y ago
      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.

clistctrl 16y ago

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 :)

giantfuzzypanda 16y ago

1. Wait until a serious attempt at proving P != NP is posted 2. Write rambling blog post and offer a ridiculous amount of money for something that now is incredibly unlikely 3. Massive page views 4. ??? 5. PROFIT!