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


For the relation between first and second look up descriptive complexity theory and finite model theory. This is a established branch of complexity theory and logic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.