Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

mlittman comments on Q&A with Michael Littman on risks from AI - Less Wrong Discussion

15 Post author: XiXiDu 19 December 2011 09:51AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (88)

You are viewing a single comment's thread. Show more comments above.

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: JoshuaZ 15 January 2012 05:41:53PM 1 point [-]

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