4 ms·

Computational Complexity Theory

89 points by sonabinu 10y ago

Sharlin 10y ago
No discussion of philosophy and complexity theory is complete without the thought-provoking paper by Aaronson [1]. [1] Aaronson, Scott. Why Philosophers Should Care About Computational Complexity. http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf
- gnudon 10y ago
  The posted URL adds a greater than sign breaking the link.
  - Sharlin 10y ago
    Doh, thanks, fixed.
jon_richards 10y ago
That site kills my scroll wheel.
zitterbewegung 10y ago
Another good resource for computational complexity theory is the computational complexity zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo . If you are just starting out you might want to start here: https://complexityzoo.uwaterloo.ca/Petting_Zoo https://complexityzoo.uwaterloo.ca/Petting_Zoo
paulpauper 10y ago
I noticed that this is posted on the Stanford philosophy portal. Does anyone else think philosophy should be considered a STEM subject (or tangentially related)? The work of Godel, Turing, and Cantor blur the lines between philosophy and mathematics. I've also noticed an immense increase in interest mathematical-philosophy in the past few years, online especially.
- infinity0 10y ago
  Some parts of philosophy are useful, when they are used to encourage interest in, or as stepping stones to, science and mathematics. But a lot of philosophy has been content with its past accomplishments, not producing any new ideas, giving up on trying to progress with certain questions [1], or else just producing bullshit that is either tautological (i.e. contains no information) or simply incoherent - e.g. "deconstruction". Science and mathematics has advanced philosophy more in the past thousand years, than philosophy has advanced itself. Aaronson has said something like this but I can't the exact quote now, but I had been thinking this earlier than that, and I'm sure countless others have too. [1] This is different from e.g. proving that a particular question is unanswerable, since this proof gives us new information to understand the world with. Philosophy has not done this, and is incapable of doing this.
  - jnbiche 10y ago
    > Science and mathematics has advanced philosophy more in the past thousand years, than philosophy has advanced itself. I'm not sure that it's that simple. Many of the most prominent mathematicians of the past 200 years considered themselves philosophers, either first or philosopher/mathematicians or philosopher/logicians: Russell, Quine, Whitehead, Peirce, Frege, Boole, Gödel, the list goes on and on. And their work often reflects their background in philosophy, with Gödel's incompleteness theorems only being the most obvious example from the works of those philosophers I listed above. And not much prior to that, math and science were really considered to be part of philosophy, and not a separate subject. I grant that certain branches and traditions of philosophy in the 20th century wandered off into nonsense and tautology, but the spirit of Russell still flows strong through those philosophy departments that emphasize logic and/or philosophy of science. And I've noticed somewhat of a resurgence lately of this wing of philosophy. In short, I think philosophy still has a lot to offer humanity, particularly in the synthesis of ideas from different science and mathematical fields. If I could go through my undergrad studies again, I think I'd double-major in philosophy and math, keeping only the Latin minor from what I earned in my actual studies (Latin helped me understand language in great depth, and I credit it with helping me pick up several foreign languages later after college). Taught well, philosophy has a reputation (probably matched only by math and physics) for teaching students how to think critically, or for finely honing that ability in students who are already critical thinkers.
Cieplak 10y ago
I wonder how many people are arbitraging proofs of P = NP. If it were a solved problem, which I suspect it is, surely folks wouldn't talk about their solutions when they could rather print money :)
- daveFNbuck 10y ago
  In all likelihood, if P = NP (which most people don't think is true) it won't be in a way that allows for practical algorithms. You won't be able to get more money by hiding such a proof than by sharing it.
  - Cieplak 10y ago
    Gödel's theorem implies that Turing machines are not complete. The problems of floating point numbers exemplify this. Our existing machine architectures operate on a discrete silicon substrate (ℤ), but we live in a continuously differentiable spacetime continuum (ℝ). I don't think this has any deep implications for P = NP, though; it's just a tooling issue.

89 points by sonabinu 10y ago

No discussion of philosophy and complexity theory is complete without the thought-provoking paper by Aaronson [1]. [1] Aaronson, Scott. Why Philosophers Should Care About Computational Complexity. http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf

gnudon 10y ago
The posted URL adds a greater than sign breaking the link.
- Sharlin 10y ago
  Doh, thanks, fixed.

jon_richards 10y ago

That site kills my scroll wheel.

zitterbewegung 10y ago

Another good resource for computational complexity theory is the computational complexity zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo . If you are just starting out you might want to start here: https://complexityzoo.uwaterloo.ca/Petting_Zoo https://complexityzoo.uwaterloo.ca/Petting_Zoo

paulpauper 10y ago

I noticed that this is posted on the Stanford philosophy portal. Does anyone else think philosophy should be considered a STEM subject (or tangentially related)? The work of Godel, Turing, and Cantor blur the lines between philosophy and mathematics. I've also noticed an immense increase in interest mathematical-philosophy in the past few years, online especially.

infinity0 10y ago
Some parts of philosophy are useful, when they are used to encourage interest in, or as stepping stones to, science and mathematics. But a lot of philosophy has been content with its past accomplishments, not producing any new ideas, giving up on trying to progress with certain questions [1], or else just producing bullshit that is either tautological (i.e. contains no information) or simply incoherent - e.g. "deconstruction". Science and mathematics has advanced philosophy more in the past thousand years, than philosophy has advanced itself. Aaronson has said something like this but I can't the exact quote now, but I had been thinking this earlier than that, and I'm sure countless others have too. [1] This is different from e.g. proving that a particular question is unanswerable, since this proof gives us new information to understand the world with. Philosophy has not done this, and is incapable of doing this.
- jnbiche 10y ago
  > Science and mathematics has advanced philosophy more in the past thousand years, than philosophy has advanced itself. I'm not sure that it's that simple. Many of the most prominent mathematicians of the past 200 years considered themselves philosophers, either first or philosopher/mathematicians or philosopher/logicians: Russell, Quine, Whitehead, Peirce, Frege, Boole, Gödel, the list goes on and on. And their work often reflects their background in philosophy, with Gödel's incompleteness theorems only being the most obvious example from the works of those philosophers I listed above. And not much prior to that, math and science were really considered to be part of philosophy, and not a separate subject. I grant that certain branches and traditions of philosophy in the 20th century wandered off into nonsense and tautology, but the spirit of Russell still flows strong through those philosophy departments that emphasize logic and/or philosophy of science. And I've noticed somewhat of a resurgence lately of this wing of philosophy. In short, I think philosophy still has a lot to offer humanity, particularly in the synthesis of ideas from different science and mathematical fields. If I could go through my undergrad studies again, I think I'd double-major in philosophy and math, keeping only the Latin minor from what I earned in my actual studies (Latin helped me understand language in great depth, and I credit it with helping me pick up several foreign languages later after college). Taught well, philosophy has a reputation (probably matched only by math and physics) for teaching students how to think critically, or for finely honing that ability in students who are already critical thinkers.

Cieplak 10y ago

I wonder how many people are arbitraging proofs of P = NP. If it were a solved problem, which I suspect it is, surely folks wouldn't talk about their solutions when they could rather print money :)

daveFNbuck 10y ago
In all likelihood, if P = NP (which most people don't think is true) it won't be in a way that allows for practical algorithms. You won't be able to get more money by hiding such a proof than by sharing it.
- Cieplak 10y ago
  Gödel's theorem implies that Turing machines are not complete. The problems of floating point numbers exemplify this. Our existing machine architectures operate on a discrete silicon substrate (ℤ), but we live in a continuously differentiable spacetime continuum (ℝ). I don't think this has any deep implications for P = NP, though; it's just a tooling issue.