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

CC BY-SA 4.0
2018-05-24T02:35:11.837Z
2018-05-24T02:35:11.837Z
Kaveh
<p>I know of at least 4 fundamentally different uses of the term "complexity theory":</p>

<ul>
<li>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.)</li>
<li>the expressiveness of a formal language</li>
<li>Kolmogorov complexity (which of course is uncomputable), or any attempts to define algorithms to approximate how hard it is to describe a phenomenon</li>
<li>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"</li>
</ul>

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

<cc.complexity-theory><kolmogorov-complexity>
Relation between different "complexity theories" and complex systems theory
lightning
# Relation between different "complexity theories" and complex systems theory

(Asked by: username_0 on 2018-05-23)

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

**Tags:** cc.complexity-theory, kolmogorov-complexity

---

## 1 answers

### Answer by username_1 on 2018-05-24. Score: 2

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.


---

