What do you think?
Rate this book
Why Philosophers Should Care About Computational Complexity
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 and 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.
59 pages, ebook
Published January 1, 2012
5 people are currently reading
210 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 4 of 4 reviews
September 29, 2020
A colleague of me recommended this essay to me, telling me that this was the decisive factor for making her change study subjects from philosophy to computer science ("computer scientists are the better logicians", she also says).
A decisive cornerstone reading in one person's life is not necessarily having the same effect on another one, especially when we're in different phases of our lives, so I didn't expect this essay to work the same way for me - after all I already have my degree in computer science and never majored in philosophy. So what does Aaronson cover here, what are the points he is trying to make?
First we need to say what kind of philosophy Aaronson is speaking about: He deals with the branch of analytical philosophy, and nothing else. The more speculative schools of continental Europe are not even slightly touched here. With this focus it is certainly easier to bring theoretical computer science and analytical philosophy together, as they both have a common language in mathematics or similar formalisms. Aaronson then recalls the fact that computability theory à la Turing or Gödel had a strong impact on philosophy and asks: Why is the same not true for complexity theory, a subject that is deeply researched in computer science after the basic questions of computability have been solved. His hypothesis is: Because to a philosopher it is immediately self-evident that it matters if something is computable or not-computable. The complexity class of a computation however seems to be only relevant for those scholars who actually deal with computations, but not necessarily for anybody outside the field. Aaronson sets out to prove this conception wrong, and he finds interesting fields of study where complexity theory can make a difference. Those fields, which are elaborated as mere examples here, are logical omniscience, machine learning and the nature of induction, quantum computing, time travel, rational behavior in economical game theory, and others. Aaronson does not provide deep discussions of such large topics, but just explains the core of the problem field on a page or two, and then adds the possible contributions of complexity theority to the field on another three or four pages. This makes for a great panorama of contemporary problems in analytical philosophy (and physics... where is the boundary?).
With my background in computer science I could easily follow that side of Aaronson's argument; with my lack of knowledge in physics I probably didn't get everything out of the parts that were discussing quantum mechanics. However, Aaronson writes a very readable idiom, and often comes up with clear similes or metaphors to explain the core of a problem. A vivid example is, when he explains the meaning of the assumption P = NP (which is believed to be false, i. e. P ≠ NP) like this: "An analogy would be if anyone able to appreciate a great symphony could also compose one themselves!"
The essay also comes with a rich bibliography and some mouthwatering suggestions for further reading. In particular I might like to have a further and deeper look at the discussion centering around machine learning and induction. Thanks to my colleague for this interesting tip!
A decisive cornerstone reading in one person's life is not necessarily having the same effect on another one, especially when we're in different phases of our lives, so I didn't expect this essay to work the same way for me - after all I already have my degree in computer science and never majored in philosophy. So what does Aaronson cover here, what are the points he is trying to make?
First we need to say what kind of philosophy Aaronson is speaking about: He deals with the branch of analytical philosophy, and nothing else. The more speculative schools of continental Europe are not even slightly touched here. With this focus it is certainly easier to bring theoretical computer science and analytical philosophy together, as they both have a common language in mathematics or similar formalisms. Aaronson then recalls the fact that computability theory à la Turing or Gödel had a strong impact on philosophy and asks: Why is the same not true for complexity theory, a subject that is deeply researched in computer science after the basic questions of computability have been solved. His hypothesis is: Because to a philosopher it is immediately self-evident that it matters if something is computable or not-computable. The complexity class of a computation however seems to be only relevant for those scholars who actually deal with computations, but not necessarily for anybody outside the field. Aaronson sets out to prove this conception wrong, and he finds interesting fields of study where complexity theory can make a difference. Those fields, which are elaborated as mere examples here, are logical omniscience, machine learning and the nature of induction, quantum computing, time travel, rational behavior in economical game theory, and others. Aaronson does not provide deep discussions of such large topics, but just explains the core of the problem field on a page or two, and then adds the possible contributions of complexity theority to the field on another three or four pages. This makes for a great panorama of contemporary problems in analytical philosophy (and physics... where is the boundary?).
With my background in computer science I could easily follow that side of Aaronson's argument; with my lack of knowledge in physics I probably didn't get everything out of the parts that were discussing quantum mechanics. However, Aaronson writes a very readable idiom, and often comes up with clear similes or metaphors to explain the core of a problem. A vivid example is, when he explains the meaning of the assumption P = NP (which is believed to be false, i. e. P ≠ NP) like this: "An analogy would be if anyone able to appreciate a great symphony could also compose one themselves!"
The essay also comes with a rich bibliography and some mouthwatering suggestions for further reading. In particular I might like to have a further and deeper look at the discussion centering around machine learning and induction. Thanks to my colleague for this interesting tip!
May 29, 2020
Galef type:
Theory 5: gives you a general concept or lens you can use to analyze many different things
Values 1: makes an explicit argument about values
Style 1: teaches principles of thinking directly
Theory 5: gives you a general concept or lens you can use to analyze many different things
Values 1: makes an explicit argument about values
Style 1: teaches principles of thinking directly
July 25, 2021
3.5/5.0
Read
July 23, 2025Admittedly nowhere near smart enough to judge this or even get most of it, but I did glean some interesting stuff from it.
Displaying 1 - 4 of 4 reviews