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?
at

3 comments:

  1. edwardahirsch2:26 AM, January 10, 2005

    One more choice is missing among (1)-(2)-(3): the complexity of discrete problems not explicitly related to computation. For example, one can study asymptotics of the number of degree-1 vertices in a graph, or the number of cycles in a graph, or the size of families of k-wise independent permutations. This is why I prefer "complexity theory" as a wider term than "computational complexity", because the former essentially captures combinatorics as well.

    ReplyDelete
  2. Anonymous11:48 AM, January 10, 2005

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

    Definitely (2). Cultural and architectural theorists (see the work of Charles Jencks for an example) have taken a fancy to the theory of complex systems, and usually just refer to it as "complexity theory". Mathematical and scientific ideas seem to filter down to the public through cultural and architectural theorists, and unfortunately, computational complexity has yet to pique their imagination. Not to say that the general public is conversant in emergent systems, but I think our field would benefit if it were as much a part of the public discourse.

    - Homin

    ReplyDelete
  3. KWRegan9:04 PM, January 23, 2005

    IMHO, 20 years ago people felt that "computational" was needed to distinguish from the "chaos theory" meanings.

    ReplyDelete