Comment author:JoshuaZ
19 December 2011 02:33:04PM
*
2 points
[-]

By far that comment is the one that is farthest outside his expertise. I'm not sure why he's commenting on it. (He is a computer scientist but none of his work seems to be in complexity theory or is even connected to it as far as I can tell.) But he's still very respected and I would presume knows a lot about issues in parts of compsci that aren't his own area of research. It is possible that he made a typo?

Comment author:mlittman
15 January 2012 03:10:40PM
6 points
[-]

Not a typo---I was mostly being cheeky. But, I have studied complexity theory quite a bit (mostly in analyzing the difficulty of problems in AI) and my 2050 number came from the following thought experiment. The problem 3-SAT is NP complete. It can be solved in time 2^n (where n is the number of variables in the formula). Over the last 20 or 30 years, people have created algorithms that solve the problem in c^n for ever decreasing values of c. If you plot the rate of decrease of c over time, it's a pretty good fit (or was 15 years ago when I did this analysis) for a line that goes below 1 in 2050. (If that happens, an NP-hard problem would be solvable in polynomial time and thus P=NP.) I don't put much stake in the idea that the future can be predicted by a graph like that, but I thought it was fun to think about. Anyhow, sorry for being flip.

Comment author:mlittman
21 January 2012 03:36:55PM
2 points
[-]

Side note: I did this analysis initially in honor of Donald Loveland (a colleague at the time whose satisfiability solver sits at the root of this tree of discoveries). I am gratified to see that he was interviewed on lesswrong on a more recent thread!

Comment author:Nymogenous
19 December 2011 01:23:52PM
*
3 points
[-]

Does anyone know what the largest amount of money wagered on this question is?

EDIT: I'm aware of a few bets on specific claimed proofs, but have not been able to find any bets on the general question that exceed a few hundred dollars (unless you count the million-dollar prizes various institutes are offering).

Comment author:gwern
19 December 2011 04:04:05PM
2 points
[-]

When I read that, I didn't expect him to actually pay up in the unlikely event the proof was right - there's a big difference between saying 'I bet my house' on your blog and actually sending a few hundred thousand or million bucks to the Long Now Foundation's Long Bets project.

Comment author:gwern
04 January 2012 02:48:36PM
*
0 points
[-]

It was an example of a more credible commitment than a blog post. To paraphrase Buffet's Noah principle, 'predicting rain doesn't count, building arks does'.

EDIT: an additional disadvantage to Long Bets is that they stash the stakes in a very low return fund (but one that should be next to invulnerable). Depending on your views about the future and your investment abilities, the opportunity cost could be substantial.

## Comments (88)

Best*6 points [-]P=NP - WTF?!? ;-)

*2 points [-]By far that comment is the one that is farthest outside his expertise. I'm not sure why he's commenting on it. (He is a computer scientist but none of his work seems to be in complexity theory or is even connected to it as far as I can tell.) But he's still very respected and I would presume knows a lot about issues in parts of compsci that aren't his own area of research. It is possible that he made a typo?

Not a typo---I was mostly being cheeky. But, I have studied complexity theory quite a bit (mostly in analyzing the difficulty of problems in AI) and my 2050 number came from the following thought experiment. The problem 3-SAT is NP complete. It can be solved in time 2^n (where n is the number of variables in the formula). Over the last 20 or 30 years, people have created algorithms that solve the problem in c^n for ever decreasing values of c. If you plot the rate of decrease of c over time, it's a pretty good fit (or was 15 years ago when I did this analysis) for a line that goes below 1 in 2050. (If that happens, an NP-hard problem would be solvable in polynomial time and thus P=NP.) I don't put much stake in the idea that the future can be predicted by a graph like that, but I thought it was fun to think about. Anyhow, sorry for being flip.

Side note: I did this analysis initially in honor of Donald Loveland (a colleague at the time whose satisfiability solver sits at the root of this tree of discoveries). I am gratified to see that he was interviewed on lesswrong on a more recent thread!

Thanks for clarifying. (And welcome to Less Wrong.)

Also see: Polls And Predictions And P=NP

*3 points [-]Does anyone know what the largest amount of money wagered on this question is?

EDIT: I'm aware of a few bets on specific claimed proofs, but have not been able to find any bets on the general question that exceed a few hundred dollars (unless you count the million-dollar prizes various institutes are offering).

Don't know, but Scott Aaronson once bet $200,000 on a proof being wrong. He wrote:

When I read that, I didn't expect him to actually pay up in the unlikely event the proof was right - there's a big difference between saying 'I bet my house' on your blog and actually sending a few hundred thousand or million bucks to the Long Now Foundation's Long Bets project.

*0 points [-]Likewise.

With Long Bets you lose the money (to your chosen charity) even if you are right, so not an ideal comparison.

*0 points [-]It was an example of a more credible commitment than a blog post. To paraphrase Buffet's Noah principle, 'predicting rain doesn't count, building arks does'.

EDIT: an additional disadvantage to Long Bets is that they stash the stakes in a very low return fund (but one that should be next to invulnerable). Depending on your views about the future and your investment abilities, the opportunity cost could be substantial.