Hacker News new | past | comments | ask | show | jobs | submit login
Computational Complexity Theory (stanford.edu)
89 points by sonabinu on Aug 13, 2016 | hide | past | favorite | 19 comments



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


The posted URL adds a greater than sign breaking the link.


Doh, thanks, fixed.


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.


At the highest level, philosophy already is part of the STEM subject. At lower levels, it's up to the teacher, but in my experience the best teachers would make me think and juggle abstract ideas, which is pretty much philosophy in a nutshell.

Philosophy as a lone subject is rather broad and less relevant, as most scientific philosophy has already transferred to STEM courses with real scientists doing a better job incorporating them in their classes.

Here is a course description lifted straight from MIT's CS course list:

> 6.833 The Human Intelligence Enterprise

> Analyzes seminal work directed at the development of a computational understanding of human intelligence, such as work on learning, language, vision, event representation, commonsense reasoning, self reflection, story understanding, and analogy. Reviews visionary ideas of Turing, Minsky, and other influential thinkers. Examines the implications of work on brain scanning, developmental psychology, and cognitive psychology. Emphasis on discussion and analysis of original papers. Requires the completion of additional exercises and a substantial term project. Enrollment limited.

http://student.mit.edu/catalog/m6c.html


Adding on, paraphrasing from Anthony Kenny in an introduction to a volumen of his book A New History of Philosophy, philosophy is affectionately called the mother of sciences. When a philosophical question, e.g. what is free will, and is there free will, develops a well-defined approach to an answer, it often splits off into its own scientific field. For example, for the question of free will, we can investigate it as politics, and examine the structures of coercion by power, as behavior and psychology, and as biological processes.


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.


> 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.


Philosophical ideas have inspired some ideas in science and mathematics indeed. New solutions to problems in science and mathematics, such as the incompleteness theorems, complexity theory, etc, have shown ways to begin answering age-old philosophical questions.

But can you give an example where a new philosophical solution, has driven advances in existing mathematical or scientific problems? My point is that this happens the other way around, much more often.

Philosophy is useful, but useless by itself. It can help you towards learning certain skills such as logical reasoning, or methods such as how to begin to formulate a problem - but if we want to correctly assign truth-values to propositions, the only tool that will allow us to do that is science and mathematics - including being able to precisely define "truth".


I definitely agree. The philosophy of science should itself be taught to all upcoming scientists and even engineers. If for nothi else than efficiency. It's as critical to properly functioning in those fields as calculus, if not more so. Next, I would throw in ethics. The STEM fields don't necessarily teach how to properly interact with fellow humans and ethics will in a broader, systemic way. Then there's logic. A basic philosophy of logic course could provide a good bridge between philosophy and computer science, math, and other fields.


I think philosophy has traditionally been more of a self-consciously humanistic pursuit, so even though there's some cross-pollination with STEM it wouldn't fit super well into that category. The thing about contemporary thought is, there's a lot of instrumentalism hidden inside it especially in high-tech circles. This arises in large part from instrumentalist prejudices in education. OTOH, the wider world of older philosophy is somewhat dangerous to modern education so it tends not to go there.


I have a friend who's a Philosophy of Science PhD candidate. The department is part of the school of Social Sciences, but they mostly hang out with physicists, mathematicians and logicians.

It's awkward.


What are their parties like? :)


Depends whether you like weird board games based on formal logic, I guess :)


Another good resource for computational complexity theory is the computational 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


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 :)


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.


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.


That site kills my scroll wheel.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: