I know of at least 4 fundamentally different uses of the term "complexity theory":
- the study of how hard a problem is to solve using some sort of computing machine (I am ignoring divisions within this category such as time vs space and parallel vs sequential models, etc.)
- the expressiveness of a formal language
- Kolmogorov complexity (which of course is uncomputable), or any attempts to define algorithms to approximate how hard it is to describe a phenomenon
- complex systems theory, which honestly as far as I can tell is a little vague and imprecise about definitions, but seems to study the property of "emergence" or "the whole being greater than its parts"
Obviously it is linguistically possible that these are four completely different concepts that happen to share a name, but have there been any attempts to connect one of the first three definitions to the fourth (complex systems theory)?