CronoDAS comments on New report: Intelligence Explosion Microeconomics - Less Wrong

45 Post author: Eliezer_Yudkowsky 29 April 2013 11:14PM

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

Comments (244)

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

Comment author: CronoDAS 15 July 2013 03:59:21AM 1 point [-]

Um... doesn't it take exponential time in order to simulate quantum mechanics on a classical computer?

Comment author: pengvado 17 July 2013 04:01:09AM *  0 points [-]

Yes (At least that's the general consensus among complexity theorists, though it hasn't been proved.) This doesn't contradict anything Eliezer said in the grandparent. The following are all consensus-but-not-proved:

P⊂BQP⊂EXP
P⊂NP⊂EXP
BQP≠NP (Neither is confidently predicted to be a subset of the other, though BQP⊂NP is at least plausible, while NP⊆BQP is not.)
If you don't measure any distinctions finer than P vs EXP, then you're using a ridiculously coarse scale. There are lots of complexity classes strictly between P and EXP, defined by limiting resources other than time-on-a-classical-computer. Some of them are tractable under our physics and some aren't.

Comment author: bogdanb 16 July 2013 02:57:13AM 0 points [-]

Is that just that we don’t know any better algorithms, or is there a proof that exptime is needed?

Comment author: CronoDAS 16 July 2013 03:33:36AM 1 point [-]

I really don't know; some Wikipedia browsing suggests that there's a proof, but I'd rather have a statement from someone who actually knows.