Thursday, November 02, 2006

Theoretical computer science is a real science

Scott Aaronson has a great post talking about some of the major discoveries in compuational complexity of the last 30 years and the implications of these discoveries for the rest of us.

It's easy to dismiss computational complexity as just "pure math" and to think that it has almost no relevance at all to the rest of science. But like pure math, major results in computational complexity can resonate throughout the scientific world (it just takes a while for those resonances to be observed!).

Scott's description of theoretical computer scientists sums it all up beautifully (and he manages to capture exactly what it is that I like about theoretical computer science):

So what are they then? Maybe it's helpful to think of them as "quantitative epistemology": discoveries about the capacities of finite beings like ourselves to learn mathematical truths. On this view, the theoretical computer scientist is basically a mathematical logician on a safari to the physical world: someone who tries to understand the universe by asking what sorts of mathematical questions can and can't be answered within it. Not whether the universe is a computer, but what kind of computer it is! Naturally, this approach to understanding the world tends to appeal most to people for whom math (and especially discrete math) is reasonably clear, whereas physics is extremely mysterious.