philosophers should care about computational complexity

One might think that, once we know something is computable, how efficiently it can be com-puted is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity the-ory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction and Goodman’s grue riddle, the foundations of quantum mechanics, economic ra-tionality, closed timelike curves, and several other topics of philosophical interest. I end b