6 ms·

Why Philosophers Should Care About Computational Complexity [pdf]

160 points by fbrusch 12y ago

diego898 12y ago
This is my favorite Scott Aaronson piece! It has been submitted to HN before, though quite some time ago. The discussion on that one is worth referencing here as well: https://news.ycombinator.com/item?id=2861825 https://news.ycombinator.com/item?id=2861825
theVirginian 12y ago
As someone with a major in philosophy, I can attest that it is in fact something we talked about often.
- j2kun 12y ago
  How deep do you go? Do you talk about P and NP? Or deeper, like interactive proofs or complexity-based definitions of randomness?
  - zenogais 12y ago
    Philosophy generally has its own language for talking about these kinds of problems, and generally its own starting points. Gilles Deleuze laid a lot of the groundwork for using ideas from chaos theory to work on philosophical problems during his life (starting with some of his work in the 1960-70s). Some links: - http://www.protevi.com/john/DG/PDF/Remarks_on_Complexity_Theory.pdf http://www.protevi.com/john/DG/PDF/Remarks_on_Complexity_The... - http://www.euppublishing.com/doi/abs/10.3366/jipt.2010.0004 http://www.euppublishing.com/doi/abs/10.3366/jipt.2010.0004 It could perhaps be useful to do similar work with computational complexity theory.
    - throwaway183839 12y ago
      What is being discussed in those links is commonly called complex systems theory[0] which is a mathematical/scientific/philosophical field concerned with how complexity (in the natural language sense of the world) arises from what appear to be simple natural laws. For example, how chaotic dynamics arise from deterministic systems, how biology arises from chemistry, or how consciousness arises from neural activity. It is connected to chaos theory, nonlinear dynamics and systems theory. It is completely different to computational complexity[1] which is what is being discussed in Aaronson's article. [0] http://en.wikipedia.org/wiki/Complex_system http://en.wikipedia.org/wiki/Complex_system [1] http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory
      - zenogais 12y ago
        My mistake, I meant it as a basis for incorporating computational complexity. The original article posted shows how computational complexity is applicable to non-linear systems, which I think are philosophically more interesting. Deleuze's work would provide some good groundwork for seeing how those kinds of ideas can be applied in a philosophical context.
- tjradcliffe 12y ago
  The difficulty is that if you get too deep into this stuff you stop doing philosophy and start doing something useful. Philosophers have to be very careful these days or they'll get dragged out of the tiny circle of darkness they insist on occupying. There is a place for philosophy, but it shrinks every time a new discovery is made. It hasn't been quite as roughly treated as theology has, but the lag is only about a century. The vast majority of what philosophers once spent their time talking about is now part of some empirically grounded special science, where making stuff up and asserting broad foundational claims without proof or testing is no longer viable. Linguistics, in particular, has carved off large chunks. Physics likewise: no fun speculating on the nature of space and time when we can pin them down pretty precisely. Various combinations of sociology, psychology, economics and political science have heavily encroached on moral philosophy. This is not to say that the world can't always use a few philosophers to poke around in the darkness and perhaps cross the boundaries of other fields to good effect, but the majority of the work that was once their exclusive preserve is now almost always better handled by people with actual, detailed, empirical knowledge of the subject. There is no value in privileging the human scale or human imagination, and fortunately no need to live within the artificial restrictions that philosophers place on themselves, particularly their refusal to do experiments or even make systematic observations to test their ideas, preferring instead to rely on "what just makes sense", because that has always worked so well in the past. Insisting on empirical testing is in no way limiting because ideas that cannot be tested are irrelevant, as they must not have any impact whatsoever on any aspect of existence (if they did, observing and/or manipulating that aspect of existence would allow the ideas related to them to be tested.) Philosophy does teach a certain kind of rigour in thinking, because without either empiricism or mathematical deduction to fall back on philosophers have to be extremely meticulous to avoid falling off the real axis entirely, but that starts to look more like a skill that ought to be taught to everyone rather than the basis for an entire academic discipline.
  - yodsanklai 12y ago
    > There is a place for philosophy, but it shrinks every time a new discovery is made. How do you define philosophy? can't we see science as as subset of philosophy?
ExpiredLink 12y ago
> The purpose of this essay was to illustrate how philosophy could be enriched by taking compu- tational complexity theory into account, much as it was enriched almost a century ago by taking computability theory into account. In particular, I argued that computational complexity provides new insights into the explanatory content of Darwinism, the nature of mathematical knowledge and proof, computationalism, syntax versus semantics, the problem of logical omniscience, debates sur- rounding the Turing Test and Chinese Room, the problem of induction, the foundations of quantum mechanics, closed timelike curves, and economic rationality. O.M.G. Yet another natural scientist trying to coerce philosophy to his 'way of thinking'.
- fbrusch 12y ago
  How can illustrating "how philosophy could be enriched", or "providing new insights" be considered "coercive"?
- j2kun 12y ago
  Aaronson studies theoretical computer science, which is a subfield of mathematics. There is no coercion in his article. He is pointing out that while philosophers like to discuss the philosophical implications of computing, they tend not to discuss the more recent developments in the field that (he argues) would aid them in eliminating faulty arguments and clarifying terms like "artificial intelligence."
- chrisdevereux 12y ago
  Right observation. Wrong target.
- deeviant 12y ago
  Yes, darn it, it's the philosopher's job to coerce people into their way of thinking, what was he thinking? In all seriousness, I think philosophy has problem, it's disconnect with reality is widening.
- syllogism 12y ago
  He isn't a natural scientist. What he's saying is, "hey, I see you're working on complicated deductive reasoning problems. Here is an adjacent field of people working on deductive reasoning problems that are relevant to what you're thinking about."
bmh100 12y ago
For me, the key insight came from the following quote regarding Searle’s Chinese Room argument [1]: *> And while it was true, the critics went on, that a giant lookup table wouldn’t “truly understand” its responses, that point is also irrelevant. For the giant lookup table is a philosophical fiction anyway: something that can’t even fit in the observable universe! If we instead imagine a compact, efficient computer program passing the Turing Test, then the situation changes drastically. For now, in order to explain how the program can be so compact and efficient, we’ll need to posit that the program includes representations of abstract concepts, capacities for learning and reasoning, and all sorts of other internal furniture that we would expect to find in a mind. Personally, I find this response to Searle extremely interesting—since if correct, it suggests that the distinction between polynomial and exponential complexity has metaphysical significance. This captures what I had intuitively thought regarding the link between computation and consciousness: consciousness is some sort of sophisticated, elegant computation embodied in human physiology. [1]: https://en.wikipedia.org/wiki/Chinese_room https://en.wikipedia.org/wiki/Chinese_room
- ZeroFries 12y ago
  This is the first good refutation of the Chinese room I've encountered. This was never mentioned in the "Minds, Brains, Machines" course I took, so I don't think it's talked about as much as it should be among philosophy of mind circles?
  - Retra 12y ago
    >This is the first good refutation of the Chinese room I've encountered. Really? I'd think that the fact that someone saying 'lookup tables aren't thinking' without ever saying what thinking is would be presenting an obviously self-refuting argument. Like a judge saying "I know crime when I see it: I don't have to write down what it is." It's simply not a basis for rational decision making, so it's certainly not a convincing assertion. The fact that anybody thinks the Chinese room is an interesting philosophical quandary is far more interesting. It means these are primitive times and you don't actually need to be very smart to beat the competition.
sinwave 12y ago
Incidentally I'm reading Sipser's book for a philosophy course right now.
azeirah 12y ago
Can someone explain to me the zero-knowledge proof example problem discussed on page 37, given two graphs G and H, prove that they are NOT isomorphic? "But as noticed by Goldreich, Micali, and Wigderson [65], there is something Merlin can do instead: he can let Arthur challenge him. Merlin can say:" Arthur, send me a new graph K, which you obtained either by randomly permuting the vertices of G, or randomly permuting the vertices of H. Then I guarantee that I will tell you, without fail, whether K ∼= G or K ∼= H. I don't understand what it means for a graph to be isomorphic to another graph, and I do not understand how Merlin's challenging answer can provide a (zero-knowledge) proof to the given problem either.
- Donwangugi 12y ago
  An isomorphism between two graphs indicates that bijection exists between two graphs, or that there exists a method to permute one graph's vertices so that they are equal to another one. What Merlin is saying to Arthur is that no matter what kind of graph K Arthur comes up with, it cannot be congruent to both G and H, or, that there exists no method to create a graph that is both G and H. Lastly it is zero-knowledge because Arthur learns nothing of the relation between G and H, only that the K he computes is not both of them simultaneously. Not sure if that helps.
- NotOscarWilde 12y ago
  A graph G is isomorphic to H if they are the same up to permuting the vertices. If you have a graph 1 -- 2 -- 3 (a path on 3 vertices, with 2 edges), it's structurally the same as 3 -- 1 -- 2, only the labels of the vertices are different, and that doesn't matter for a graph theorist. So we say the graphs are isomorphic. I had a hard time understanding what it means when I was in undergraduate school, because it seems so trivial -- why can't I say that the graphs are simply the same, like 1 = 1 or {0} = {0}? You could say they are the same, but the interesting point is that it is not easy to decide whether they are the same if the two graphs G and H are big. Therefore, "graph isomorphism" is a computational problem in its own right.
talles 12y ago
I love when computing mixes with philosophy, despite being unable to grasp most of it. Take for instance Rich Hickey's Are We There Yet?[1], the Alfred North Whitehead quotes are great food for thought: you dive into it just as much you are able to swim. [1]: http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hic...
raincom 12y ago
It is like saying "Philosophers should care about biology or about some other domain X". If you look at the history of "Philosophy of sciences", most of them came from the object-level domains. In other words, many philosophers of sciences came trained from domains such as physics, etc. Pierre Duhem was a physicist. But he also contributed to philsophy of scineces: check the famoous Duhem-Quine thesis. Same thing happend to "philosophy of biology". If you look at the journal "philosphy of biology", most of the early contributors came from biology. I think, Scott Aaronson is aware of the controversy between Oded Goldreich and Neal Koblitz. This controversy could have been formulated better if people in theoretical computer scince had mastered "philosophy of sciences. People in Artificial Intelligence (esp of CS variety) make wild claims like AI annihilating the human race. And these voices have strong backing from people like Bill Gates. However, these voices don't look at what philosophers have writtern about AI, and the kind of nonsense AI folks spew. Yes, AI can solve particular tasks (a chess game, autonomous driving): but can it replace humans? Yes, say the AI group; No, say the philosopher Hubert Dreyfus. Check the latter's book: What computers can't do, a critique of artificial reason.
diego898 12y ago
Scott just gave a fantastic Nautil.us interview! Just placing here for completions sake: HN link [1] and direct link [2] [1]: https://news.ycombinator.com/item?id=9074033 https://news.ycombinator.com/item?id=9074033 [2]: http://nautil.us/issue/21/information/ingenious-scott-aaronson http://nautil.us/issue/21/information/ingenious-scott-aarons...

160 points by fbrusch 12y ago

This is my favorite Scott Aaronson piece! It has been submitted to HN before, though quite some time ago. The discussion on that one is worth referencing here as well: https://news.ycombinator.com/item?id=2861825 https://news.ycombinator.com/item?id=2861825

theVirginian 12y ago

As someone with a major in philosophy, I can attest that it is in fact something we talked about often.

j2kun 12y ago
How deep do you go? Do you talk about P and NP? Or deeper, like interactive proofs or complexity-based definitions of randomness?
- zenogais 12y ago
  Philosophy generally has its own language for talking about these kinds of problems, and generally its own starting points. Gilles Deleuze laid a lot of the groundwork for using ideas from chaos theory to work on philosophical problems during his life (starting with some of his work in the 1960-70s). Some links: - http://www.protevi.com/john/DG/PDF/Remarks_on_Complexity_Theory.pdf http://www.protevi.com/john/DG/PDF/Remarks_on_Complexity_The... - http://www.euppublishing.com/doi/abs/10.3366/jipt.2010.0004 http://www.euppublishing.com/doi/abs/10.3366/jipt.2010.0004 It could perhaps be useful to do similar work with computational complexity theory.
  - throwaway183839 12y ago
    What is being discussed in those links is commonly called complex systems theory[0] which is a mathematical/scientific/philosophical field concerned with how complexity (in the natural language sense of the world) arises from what appear to be simple natural laws. For example, how chaotic dynamics arise from deterministic systems, how biology arises from chemistry, or how consciousness arises from neural activity. It is connected to chaos theory, nonlinear dynamics and systems theory. It is completely different to computational complexity[1] which is what is being discussed in Aaronson's article. [0] http://en.wikipedia.org/wiki/Complex_system http://en.wikipedia.org/wiki/Complex_system [1] http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory
    - zenogais 12y ago
      My mistake, I meant it as a basis for incorporating computational complexity. The original article posted shows how computational complexity is applicable to non-linear systems, which I think are philosophically more interesting. Deleuze's work would provide some good groundwork for seeing how those kinds of ideas can be applied in a philosophical context.
tjradcliffe 12y ago
The difficulty is that if you get too deep into this stuff you stop doing philosophy and start doing something useful. Philosophers have to be very careful these days or they'll get dragged out of the tiny circle of darkness they insist on occupying. There is a place for philosophy, but it shrinks every time a new discovery is made. It hasn't been quite as roughly treated as theology has, but the lag is only about a century. The vast majority of what philosophers once spent their time talking about is now part of some empirically grounded special science, where making stuff up and asserting broad foundational claims without proof or testing is no longer viable. Linguistics, in particular, has carved off large chunks. Physics likewise: no fun speculating on the nature of space and time when we can pin them down pretty precisely. Various combinations of sociology, psychology, economics and political science have heavily encroached on moral philosophy. This is not to say that the world can't always use a few philosophers to poke around in the darkness and perhaps cross the boundaries of other fields to good effect, but the majority of the work that was once their exclusive preserve is now almost always better handled by people with actual, detailed, empirical knowledge of the subject. There is no value in privileging the human scale or human imagination, and fortunately no need to live within the artificial restrictions that philosophers place on themselves, particularly their refusal to do experiments or even make systematic observations to test their ideas, preferring instead to rely on "what just makes sense", because that has always worked so well in the past. Insisting on empirical testing is in no way limiting because ideas that cannot be tested are irrelevant, as they must not have any impact whatsoever on any aspect of existence (if they did, observing and/or manipulating that aspect of existence would allow the ideas related to them to be tested.) Philosophy does teach a certain kind of rigour in thinking, because without either empiricism or mathematical deduction to fall back on philosophers have to be extremely meticulous to avoid falling off the real axis entirely, but that starts to look more like a skill that ought to be taught to everyone rather than the basis for an entire academic discipline.
- yodsanklai 12y ago
  > There is a place for philosophy, but it shrinks every time a new discovery is made. How do you define philosophy? can't we see science as as subset of philosophy?

ExpiredLink 12y ago

> The purpose of this essay was to illustrate how philosophy could be enriched by taking compu- tational complexity theory into account, much as it was enriched almost a century ago by taking computability theory into account. In particular, I argued that computational complexity provides new insights into the explanatory content of Darwinism, the nature of mathematical knowledge and proof, computationalism, syntax versus semantics, the problem of logical omniscience, debates sur- rounding the Turing Test and Chinese Room, the problem of induction, the foundations of quantum mechanics, closed timelike curves, and economic rationality. O.M.G. Yet another natural scientist trying to coerce philosophy to his 'way of thinking'.

fbrusch 12y ago
How can illustrating "how philosophy could be enriched", or "providing new insights" be considered "coercive"?
j2kun 12y ago
Aaronson studies theoretical computer science, which is a subfield of mathematics. There is no coercion in his article. He is pointing out that while philosophers like to discuss the philosophical implications of computing, they tend not to discuss the more recent developments in the field that (he argues) would aid them in eliminating faulty arguments and clarifying terms like "artificial intelligence."
chrisdevereux 12y ago
Right observation. Wrong target.
deeviant 12y ago
Yes, darn it, it's the philosopher's job to coerce people into their way of thinking, what was he thinking? In all seriousness, I think philosophy has problem, it's disconnect with reality is widening.
syllogism 12y ago
He isn't a natural scientist. What he's saying is, "hey, I see you're working on complicated deductive reasoning problems. Here is an adjacent field of people working on deductive reasoning problems that are relevant to what you're thinking about."

bmh100 12y ago

For me, the key insight came from the following quote regarding Searle’s Chinese Room argument [1]: *> And while it was true, the critics went on, that a giant lookup table wouldn’t “truly understand” its responses, that point is also irrelevant. For the giant lookup table is a philosophical fiction anyway: something that can’t even fit in the observable universe! If we instead imagine a compact, efficient computer program passing the Turing Test, then the situation changes drastically. For now, in order to explain how the program can be so compact and efficient, we’ll need to posit that the program includes representations of abstract concepts, capacities for learning and reasoning, and all sorts of other internal furniture that we would expect to find in a mind. Personally, I find this response to Searle extremely interesting—since if correct, it suggests that the distinction between polynomial and exponential complexity has metaphysical significance. This captures what I had intuitively thought regarding the link between computation and consciousness: consciousness is some sort of sophisticated, elegant computation embodied in human physiology. [1]: https://en.wikipedia.org/wiki/Chinese_room https://en.wikipedia.org/wiki/Chinese_room

ZeroFries 12y ago
This is the first good refutation of the Chinese room I've encountered. This was never mentioned in the "Minds, Brains, Machines" course I took, so I don't think it's talked about as much as it should be among philosophy of mind circles?
- Retra 12y ago
  >This is the first good refutation of the Chinese room I've encountered. Really? I'd think that the fact that someone saying 'lookup tables aren't thinking' without ever saying what thinking is would be presenting an obviously self-refuting argument. Like a judge saying "I know crime when I see it: I don't have to write down what it is." It's simply not a basis for rational decision making, so it's certainly not a convincing assertion. The fact that anybody thinks the Chinese room is an interesting philosophical quandary is far more interesting. It means these are primitive times and you don't actually need to be very smart to beat the competition.

sinwave 12y ago

Incidentally I'm reading Sipser's book for a philosophy course right now.

azeirah 12y ago

Can someone explain to me the zero-knowledge proof example problem discussed on page 37, given two graphs G and H, prove that they are NOT isomorphic? "But as noticed by Goldreich, Micali, and Wigderson [65], there is something Merlin can do instead: he can let Arthur challenge him. Merlin can say:" Arthur, send me a new graph K, which you obtained either by randomly permuting the vertices of G, or randomly permuting the vertices of H. Then I guarantee that I will tell you, without fail, whether K ∼= G or K ∼= H. I don't understand what it means for a graph to be isomorphic to another graph, and I do not understand how Merlin's challenging answer can provide a (zero-knowledge) proof to the given problem either.

Donwangugi 12y ago
An isomorphism between two graphs indicates that bijection exists between two graphs, or that there exists a method to permute one graph's vertices so that they are equal to another one. What Merlin is saying to Arthur is that no matter what kind of graph K Arthur comes up with, it cannot be congruent to both G and H, or, that there exists no method to create a graph that is both G and H. Lastly it is zero-knowledge because Arthur learns nothing of the relation between G and H, only that the K he computes is not both of them simultaneously. Not sure if that helps.
NotOscarWilde 12y ago
A graph G is isomorphic to H if they are the same up to permuting the vertices. If you have a graph 1 -- 2 -- 3 (a path on 3 vertices, with 2 edges), it's structurally the same as 3 -- 1 -- 2, only the labels of the vertices are different, and that doesn't matter for a graph theorist. So we say the graphs are isomorphic. I had a hard time understanding what it means when I was in undergraduate school, because it seems so trivial -- why can't I say that the graphs are simply the same, like 1 = 1 or {0} = {0}? You could say they are the same, but the interesting point is that it is not easy to decide whether they are the same if the two graphs G and H are big. Therefore, "graph isomorphism" is a computational problem in its own right.

talles 12y ago

I love when computing mixes with philosophy, despite being unable to grasp most of it. Take for instance Rich Hickey's Are We There Yet?[1], the Alfred North Whitehead quotes are great food for thought: you dive into it just as much you are able to swim. [1]: http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hic...

raincom 12y ago

It is like saying "Philosophers should care about biology or about some other domain X". If you look at the history of "Philosophy of sciences", most of them came from the object-level domains. In other words, many philosophers of sciences came trained from domains such as physics, etc. Pierre Duhem was a physicist. But he also contributed to philsophy of scineces: check the famoous Duhem-Quine thesis. Same thing happend to "philosophy of biology". If you look at the journal "philosphy of biology", most of the early contributors came from biology. I think, Scott Aaronson is aware of the controversy between Oded Goldreich and Neal Koblitz. This controversy could have been formulated better if people in theoretical computer scince had mastered "philosophy of sciences. People in Artificial Intelligence (esp of CS variety) make wild claims like AI annihilating the human race. And these voices have strong backing from people like Bill Gates. However, these voices don't look at what philosophers have writtern about AI, and the kind of nonsense AI folks spew. Yes, AI can solve particular tasks (a chess game, autonomous driving): but can it replace humans? Yes, say the AI group; No, say the philosopher Hubert Dreyfus. Check the latter's book: What computers can't do, a critique of artificial reason.

diego898 12y ago

Scott just gave a fantastic Nautil.us interview! Just placing here for completions sake: HN link [1] and direct link [2] [1]: https://news.ycombinator.com/item?id=9074033 https://news.ycombinator.com/item?id=9074033 [2]: http://nautil.us/issue/21/information/ingenious-scott-aaronson http://nautil.us/issue/21/information/ingenious-scott-aarons...