7 ms·

Why Philosophers Should Care About Computational Complexity (2011) [pdf]

173 points by alokrai 8y ago

1996 8y ago
Missing #1: Because it will help with tenure and their future publication career (no, not really, so they don't)
mlthoughts2018 8y ago
Previously discussed on HN: - https://news.ycombinator.com/item?id=2861825 https://news.ycombinator.com/item?id=2861825 - https://news.ycombinator.com/item?id=2897277 https://news.ycombinator.com/item?id=2897277 - https://news.ycombinator.com/item?id=11913825 https://news.ycombinator.com/item?id=11913825
- fergie 8y ago
  Thanks- I missed it all of those times so I am glad it was reposted, and also glad that you have linked to the previous conversations.
- no_identd 8y ago
  Citations here: https://scholar.google.com/scholar?cites=14675126185841895424 https://scholar.google.com/scholar?cites=1467512618584189542...
danharaj 8y ago
The method of proof of P!=NP will undoubtedly tell us something deeply fundamental about computation and therefore logic and therefore philosophy. That complexity theory is so difficult thus far is in itself philosophically interesting.
- goldenkey 8y ago
  Seems directly related to philosophy via the Busy Beaver[1] function. Every statement about all integers, ie. Goldbach's conjecture, can map to a predicate P(n). P(n) is either true for all integers or fails at a least n. This least n must be less than BB(program_size(P)). We can look at the predicates that don't fail, and take their negation also, ~P(n), which clearly does fail at n=1. These predicates are all P such that P(1) is true or ∄n P(n) is true. They take up a percentage of the space of all predicates (analog of Chaitin's constant[2]). Meaning that in the distribution of all possible predicates, a certain proportion are just (∞,1) and (1,∞) mappings, while the rest of the predicates have mappings bounded by their program size. It seems that because of the pigeonhole principle and the mappings already "wasted" on (1,∞) and (∞,1), the rest of our distribution gets restricted to bounded levels of expressive power. The literal allowance of statements that are false trivially, or true for everything, limits the power of all of the remaining statements that now have to position themselves as finitary AND confined by that proportionality. The universe is a very weird place. [1] https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver [2] http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant
tek-cyb-org 8y ago
szabo
Animats 8y ago
That's a useful article. The easy parts include - The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that. - The same scaling issue applies to the "Chinese room", which is an extremely inefficient solution to the problem. The question is how much can you improve on exhaustive enumeration. Then it gets hard. I thought it was established that quantum computing is not going to allow brute-force search (using multiple universes?) on problems like factoring. Is that wrong?
- Pica_soO 8y ago
  - The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that. Are you sure on that one? A system with finite memory can computate procedural, fractal, infinite equations and as long as it looses the state it started from - progress infinitely on this way back and forth. Thus even a limited system can computate eternally, and a program to proof this to be a correct program with a finite holding state, will follow this eternally into the abyss of computation.
  - TeMPOraL 8y ago
    I think memory includes all program state, so at some point in the fractal computation you're bound to hit a memory state you've seen before - and since that state contains all that determines the program evolution, you can stop here and say that it won't finish.
    - Pica_soO 8y ago
      Im sorry, but that seems.. unsound.. If i remember Cantors infinity theorem correctly, you can recombine sets to basically proof that the resulting set is bigger then the original sets. Now the naive assumption is that to recombine a set, you have to have the original sets "stored" somewhere. But assuming you have enough computation time, you can travel lightly - aka have tail-call eliminated recursive threads go back to the origins of such a set, following a formula and recompute both the values. Thus, you could have infinite reasonable work to do, with finite computation power?

173 points by alokrai 8y ago

1996 8y ago

Missing #1: Because it will help with tenure and their future publication career (no, not really, so they don't)

mlthoughts2018 8y ago

Previously discussed on HN: - https://news.ycombinator.com/item?id=2861825 https://news.ycombinator.com/item?id=2861825 - https://news.ycombinator.com/item?id=2897277 https://news.ycombinator.com/item?id=2897277 - https://news.ycombinator.com/item?id=11913825 https://news.ycombinator.com/item?id=11913825

fergie 8y ago
Thanks- I missed it all of those times so I am glad it was reposted, and also glad that you have linked to the previous conversations.
no_identd 8y ago
Citations here: https://scholar.google.com/scholar?cites=14675126185841895424 https://scholar.google.com/scholar?cites=1467512618584189542...

danharaj 8y ago

The method of proof of P!=NP will undoubtedly tell us something deeply fundamental about computation and therefore logic and therefore philosophy. That complexity theory is so difficult thus far is in itself philosophically interesting.

goldenkey 8y ago
Seems directly related to philosophy via the Busy Beaver[1] function. Every statement about all integers, ie. Goldbach's conjecture, can map to a predicate P(n). P(n) is either true for all integers or fails at a least n. This least n must be less than BB(program_size(P)). We can look at the predicates that don't fail, and take their negation also, ~P(n), which clearly does fail at n=1. These predicates are all P such that P(1) is true or ∄n P(n) is true. They take up a percentage of the space of all predicates (analog of Chaitin's constant[2]). Meaning that in the distribution of all possible predicates, a certain proportion are just (∞,1) and (1,∞) mappings, while the rest of the predicates have mappings bounded by their program size. It seems that because of the pigeonhole principle and the mappings already "wasted" on (1,∞) and (∞,1), the rest of our distribution gets restricted to bounded levels of expressive power. The literal allowance of statements that are false trivially, or true for everything, limits the power of all of the remaining statements that now have to position themselves as finitary AND confined by that proportionality. The universe is a very weird place. [1] https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver [2] http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant

tek-cyb-org 8y ago

szabo

Animats 8y ago

That's a useful article. The easy parts include - The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that. - The same scaling issue applies to the "Chinese room", which is an extremely inefficient solution to the problem. The question is how much can you improve on exhaustive enumeration. Then it gets hard. I thought it was established that quantum computing is not going to allow brute-force search (using multiple universes?) on problems like factoring. Is that wrong?

Pica_soO 8y ago
- The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that. Are you sure on that one? A system with finite memory can computate procedural, fractal, infinite equations and as long as it looses the state it started from - progress infinitely on this way back and forth. Thus even a limited system can computate eternally, and a program to proof this to be a correct program with a finite holding state, will follow this eternally into the abyss of computation.
- TeMPOraL 8y ago
  I think memory includes all program state, so at some point in the fractal computation you're bound to hit a memory state you've seen before - and since that state contains all that determines the program evolution, you can stop here and say that it won't finish.
  - Pica_soO 8y ago
    Im sorry, but that seems.. unsound.. If i remember Cantors infinity theorem correctly, you can recombine sets to basically proof that the resulting set is bigger then the original sets. Now the naive assumption is that to recombine a set, you have to have the original sets "stored" somewhere. But assuming you have enough computation time, you can travel lightly - aka have tail-call eliminated recursive threads go back to the origins of such a set, following a formula and recompute both the values. Thus, you could have infinite reasonable work to do, with finite computation power?