Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Philosophers Should Care About Computational Complexity

scottaaronson.com

Post reply on HN
Print view View original

11–20 of 38 posts

Re: Why Philosophers Should Care About Computational Complexity

#11

Post by psykotic »

strlen wrote: post #8
gwern wrote: post #5

Earlier quoted context omitted.

> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic. Aaronson covers this, pointing out that those results are both in computability theory, not complexity .

Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines. Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.

> (much like NP-Complete problems are a subset of Complete problems)

That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."

Re: Why Philosophers Should Care About Computational Complexity

#12

Post by Sniffnoy »

strlen wrote: post #8
gwern wrote: post #5

Earlier quoted context omitted.

> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic. Aaronson covers this, pointing out that those results are both in computability theory, not complexity .

Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines. Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.

> I always thought of complexity as being a subset of computability theory

But while that's certainly true in a sense, that doesn't imply what you stated -- just because they care about computability theory doesn't mean they care about this aspect of it.

Re: Why Philosophers Should Care About Computational Complexity

#13

Post by Sniffnoy »

psykotic wrote: post #11
strlen wrote: post #8

Earlier quoted context omitted.

Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines. Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.

> (much like NP-Complete problems are a subset of Complete problems) That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."

Or perhaps he meant that NP-complete problems are a subset of NP-hard problems? But that wouldn't be analogous...

(Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's intermediate? Is this something that's known?)

Re: Why Philosophers Should Care About Computational Complexity

#15

Post by psykotic »

Sniffnoy wrote: post #13
psykotic wrote: post #11

Earlier quoted context omitted.

> (much like NP-Complete problems are a subset of Complete problems) That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."

Or perhaps he meant that NP-complete problems are a subset of NP-hard problems? But that wouldn't be analogous... (Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's inter…

I hate it when a pedantic correction backfires. I should have been more careful. :)

You're right to raise that question. It's a classical result of computability theory that there exists an undecidable problem that is strictly easier than the halting problem: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_...

Re: Why Philosophers Should Care About Computational Complexity

#16

Post by forkandwait »

The problem with Godel and friends is that they point to the limits of rationality. Without a transcendent rationality (and morality) upon which to discurse, philosophers are out of a job, so to speak. If you use logic to understand everything, the last thing you want to deal with is somebody telling you the limits to logic. So they blow him off.

At least I think the above is true for "analytic" philosophers. The "continentals", on the other hand, have been engaging in an extended attack on transcendent rationality since Nietszche who said, to paraphrase, that every transcendent metaphysics was an attempt to justify a morality, and every morality was facilitated a (usually inarticulate) "will to power." (This line sort of starts with Hegel, who posited that rationality emerged from history and the development of a collective human spirit, but wasn't "out there" before that). Godel seems like ammunition for these guys, but I don't think they have picked him up much. I guess if you are anti-rationalist, the last thing you read up on is advanced logic, even if it is so advanced it comes to its own frontier.

Re: Why Philosophers Should Care About Computational Complexity

#17

Post by joe_the_user »

forkandwait wrote: post #16

The problem with Godel and friends is that they point to the limits of rationality. Without a transcendent rationality (and morality) upon which to discurse, philosophers are out of a job, so to speak. If you use logic to understand everything, the last thing you want to deal with is somebody telling you the limits to logic. So they blow him off. At least I think the above is true for "analytic" philosophers. The "co…

I believe Alain Badiou might be an exception here.

http://en.wikipedia.org/wiki/Alain_Badiou

Re: Why Philosophers Should Care About Computational Complexity

#18

Post by Sniffnoy »

psykotic wrote: post #15
Sniffnoy wrote: post #13

Earlier quoted context omitted.

Or perhaps he meant that NP-complete problems are a subset of NP-hard problems? But that wouldn't be analogous... (Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's inter…

I hate it when a pedantic correction backfires. I should have been more careful. :) You're right to raise that question. It's a classical result of computability theory that there exists an undecidable problem that is strictly easier than the halting problem: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_...

Also I just realized that just because something is at least as hard as the halting problem, doesn't necessarily mean it stays so when you restrict to polynomial-time reductions. So maybe even what I stated above isn't true. :-/ Well, the halting problem is NP-hard, at any rate. :P

Re: Why Philosophers Should Care About Computational Complexity

#19

Post by ubernostrum »

forkandwait wrote: post #16

The problem with Godel and friends is that they point to the limits of rationality. Without a transcendent rationality (and morality) upon which to discurse, philosophers are out of a job, so to speak. If you use logic to understand everything, the last thing you want to deal with is somebody telling you the limits to logic. So they blow him off. At least I think the above is true for "analytic" philosophers. The "co…

Um, OK. There's a lot wrong here.

For starters, philosophers are plenty comfortable with the limits of rationality, and were poking at that long before Gödel came along. Similarly, "using logic to understand everything" is a pretty sweeping generalization, and one which quite likely commits an equivocation the way you're trying to use it.

As for analytic philosophy, well, you seem to have a lot of misconceptions about what exactly that means. Analytic philosophy's certainly done its fair share of dumb things, but blowing off Gödel for showing "the limits to logic"? Not sure where you get that one from; for the most part, analytic philosophers have been spending the last century or so on things like the problem of demarcation; Gödel's work with respect to formal systems is basically irrelevant to that and to plenty of other things philosophers spend their time on.

Post reply on HN