Sunday, January 09, 2005
What's in a Name? Complexity (by guest blogger Rahul Santhanam)
Hullo, all. Nice of Lance to lease me this space for a week, I most sincerely hope he won't come to regret it. I was thinking about names. Lance is most economical, so why the "computational" in "computational complexity"? Any theory attempts to understand and explain complexity, so it's no surprise there's an ambiguity about the term "complexity theory". A complexity theorist could be (1) one of us, i.e., someone studying the complexity of solving discrete mathematical problems (2) someone studying the evolution of complex dynamical systems with reference to phenomena such as chaos, self-organized criticality, emergent structures and suchlike (3) someone studying the complexity of doing continuous mathematics, where only partial information is available about the input. And there may be further incarnations of which I am unaware. Journal names are instructive - the journal "Complexity" hosts theorists of type (2), "Journal of Complexity" harbors theorists of stripe (3), and of course we have "Computational Complexity" to ourselves. I wonder: when a non-scientist who is curious about science hears the term "complexity theorist", which of the above does he visualize? (2), most probably. I remember reading Mitchell Waldrop's book "Complexity" as an undergrad, and there have been several other popular books of the same flavor. Has computational complexity failed to reach out to a wider audience and define itself, or is it rather that we have aspired to a different goal: acknowledgement by the mathematics community of our significance?