Saturday, November 12, 2011

What is Theoretical Computer Science?

Some people study Number Theory. Others study the Geometry of Manifolds. In TCS, we study the Power of Computation. We prove theorems, just like in any other pure science. What can be computed, how well, how fast, with what techniques, and what are the limitations? In the same way that number theorists were long fixated on Fermat's conjecture, our eyes are fixed on the distant P versus NP problem. Instances of applied problems are a chance for us to test our understanding of the hidden structure. "Reality check" means an example against which to confront our ideas on computation. Whenever a problem is hard in theory but easy in practice, or vice-versa, it's an invitation to revisit our assumptions and refine our models.

The real world is useful, as a tool towards developing a better theory.

2 comments:

  1. I like this way of talking about TCS and its role and how it is developing. Especially I liked your "Whenever a problem is hard in theory but easy in practice, or vice-versa, …". I think this is what Kuhn would call an ignition for a [small] paradigm change.

    ReplyDelete

Note: Only a member of this blog may post a comment.