[Computational Complexity] Why Computer Science Theory Matters?
At the AAAS Annual Meeting on Friday, the CRA organized a session Computer Science Behind Your Science. Bernard Chazelle gave one of the talks Why Computer Science Theory Matters? based on an essay he wrote for the undergraduate magazine Math Horizons. In a pre-talk interview Chazelle argues that algorithms can help us explain scientific ideas in a fundamentally different way than simple mathematical formula.
Computer science is a new way of thinking, a new way of looking at things. For example, mathematics can't come near to describing the complexity of human endeavors in the way that computer science can. To make a literary analogy, mathematics produces the equivalent of one-liners – equations that are pithy, insightful, brilliant. Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex. But that is exactly what makes it unique and appealing — computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot.When one asks scientists in other disciplines what role computer science has for them, one usually sees CS as a way to solve their large computational problems, like large matrix computations. The more enlightened realize the importance of algorithmic issues and even have a rough understanding of NP-completeness and what that means for the problems they would like to solve. But we haven't on a large scale made scientists in other fields realize that computation exists within the systems they study. Protein folding, economic markets, the ways astronomical bodies interact are all computational processes and once we can make this case, the ideas and tools of computational complexity and theoretical computer science can help them understand the strengths and limitations of these processes.