Why Philosophers Should Care About Computational Complexity

Details Why Philosophers Should Care About Computational Complexity Why Philosophers Should Care About Computational Complexity

2011-08-08

arxiv.org/abs/1108.1791v3

Computer Science

Computational Complexity

58 pages, to appear in "Computability: G\"odel, Turing, Church, and beyond," MIT Press, 2012. Some minor clarifications and co

Scientific paper

One might think that, once we know something is computable, how efficiently it can be computed 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 theory---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, Goodman's grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.

Affiliated with

Also associated with

No associations

Rating

Why Philosophers Should Care About Computational Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Why Philosophers Should Care About Computational Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Why Philosophers Should Care About Computational Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-190815