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

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

15 19 December 2011 09:51AM

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

Sort By: Best

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

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