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!

## Comments (88)

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