Why philosophers should care about computational complexity

Read this paper a month or two back.  It's a truly fascinating discussion of the mathematics of computational complexity ("How hard is it to find an answer to a problem in class X using algorithm Y?") and its implications for some puzzles in philosophy.

Turns out that understanding complexity classes can add a lot to the way we think about our own minds. Examples include:

• Do I "know" what 1,847,234 times 345 is?
• Is it possible to cheat on the Turing test?
• Can waterfalls think?
• When can you prove you know something without revealing *how* you know it?
• If my grandkids learn to time travel, do I have to worry they might kill me?

There's math, but Aaronson has gone to a lot of effort to keep it manageable and well-explained. Highly recommend it.

(BTW, the paper has been out there for a few months. I'm posting now because it's related--a little--to the review of computational social science I've been working on.)