tag:blogger.com,1999:blog-3722233.post110531368228769456..comments2020-01-23T21:34:59.362-05:00Comments on Computational Complexity: What's in a Name? Complexity (by guest blogger Rahul Santhanam)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1106535845977975332005-01-23T22:04:00.000-05:002005-01-23T22:04:00.000-05:00IMHO, 20 years ago people felt that "computational...IMHO, 20 years ago people felt that "computational" was needed to distinguish from the "chaos theory" meanings.Ken Reganhttps://www.blogger.com/profile/06096073630081306116noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105379305384528132005-01-10T12:48:00.000-05:002005-01-10T12:48:00.000-05:00>I wonder: when a non-scientist who is curious abo...>I wonder: when a non-scientist who is curious about <br />>science hears the term "complexity theorist", which <br />>of the above does he visualize? (2), most probably.<br /><br />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.<br /><br />- HominAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105345596992912922005-01-10T03:26:00.000-05:002005-01-10T03:26:00.000-05:00One more choice is missing among (1)-(2)-(3): the ...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.edwardahirschhttps://www.blogger.com/profile/18094179693219521111noreply@blogger.com