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!
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).
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.
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.
P=NP—WTF?!? ;-)
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
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.
Likewise.
With Long Bets you lose the money (to your chosen charity) even if you are right, so not an ideal comparison.
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.