<p><em>In general, there are two types of 'complexity' that are studied. Usually, when people talk about 'complexity', especially on the internet, they mean Santa Fe Institute style complexity. This is a vague and poorly defined concept that has struggled for a number of years without making significant progress. It uses pretty words, but has yet to deliver on any real results. I will not discuss it more in this answer.</em></p>

<p>The other type of complexity is <a href="http://en.wikipedia.org/wiki/Computational_complexity_theory" rel="nofollow noreferrer">computational complexity theory</a> as studied by theoretical computer science. In general, this field is <a href="https://cogsci.stackexchange.com/a/4807/29">too mathematical and too rigorous to engage with most of cognitive science and psychology</a>, but there are a few connections. I recommend looking at the cstheory question: <a href="https://cstheory.stackexchange.com/q/5379/1037">What is the complexity class most closely associated with what the human mind can accomplish quickly?</a></p>

<p>In that question, the author is curious to know which <a href="http://en.wikipedia.org/wiki/Complexity_class" rel="nofollow noreferrer">complexity class</a> most closely resembles what humans can achieve. My favourite <a href="https://cstheory.stackexchange.com/a/5388/1037">answer</a> discusses the <strong>Tractable Cognition thesis</strong>. For reference, see these papers:</p>

<ul>
<li>Iris van Rooij. <a href="http://staff.science.uva.nl/~szymanik/papers/TractableCognition.pdf" rel="nofollow noreferrer">The Tractable Cognition thesis</a>. Cognitive Science, 32, pp. 939-984, 2008.</li>
<li>Iris van Rooij. Parameters that make Cognitive Work Light. <a href="http://www.mrfellows.net/Newsletters/2009June_FPT_News.pdf" rel="nofollow noreferrer">FPT News: Parameterized Complexity Newsletter, June 2009</a>.</li>
</ul>

<p>A specialized part of computational complexity known as <a href="http://en.wikipedia.org/wiki/Computational_learning_theory" rel="nofollow noreferrer">computational learning theory</a> has been particularily notable in trying to make connections to cognitive science, in particular linguists. <a href="http://www.lps.uci.edu/~johnsonk/Publications/Johnson.GoldsTheorem.pdf" rel="nofollow noreferrer">Gold's theorem</a> on the non-learnability of certain families of formal languages was especially relevant in the early days of the <a href="http://en.wikipedia.org/wiki/Poverty_of_the_stimulus" rel="nofollow noreferrer">poverty of the stimulus</a> debate. You can learn more about it in these two questions:</p>

<ul>
<li><a href="https://cogsci.stackexchange.com/q/985/29">Applications of computational learning theory in the cognitive sciences</a></li>
<li><a href="https://linguistics.stackexchange.com/q/1066/33">General mathematical frameworks of language acquisition since Gold</a></li>
</ul>

<p>Keep in mind, that computational complexity is advanced material and requires a decent mathematical sophistication. However, with difficulty comes insights.</p>

CC BY-SA 3.0
2013-07-12T05:04:35.093Z
2013-12-04T18:45:28.883Z
2017-04-13T12:56:16.417Z
Artem Kaznatcheev
<ul>
<li>Does complexity theory speak to cognitive science?</li>
<li>If yes, where can I find some material to explore that is suitable for undergraduate level understanding?</li>
<li>In particular, is there any audio contennt on this?</li>
</ul>

<reference-request><cognitive-modeling><philosophy-of-mind><mathematical-psychology>
What introductory material is available linking complexity theory to cognitive science?
Analogue girl
# What introductory material is available linking complexity theory to cognitive science?

(Asked by: username_0 on 2013-07-12)

* Does complexity theory speak to cognitive science?
* If yes, where can I find some material to explore that is suitable for undergraduate level understanding?
* In particular, is there any audio contennt on this?

**Tags:** reference-request, cognitive-modeling, philosophy-of-mind, mathematical-psychology


---

## 1 answers

### Answer by username_1 on 2013-07-12. Score: 8

*In general, there are two types of 'complexity' that are studied. Usually, when people talk about 'complexity', especially on the internet, they mean Santa Fe Institute style complexity. This is a vague and poorly defined concept that has struggled for a number of years without making significant progress. It uses pretty words, but has yet to deliver on any real results. I will not discuss it more in this answer.*

The other type of complexity is [computational complexity theory](http://en.wikipedia.org/wiki/Computational_complexity_theory) as studied by theoretical computer science. In general, this field is [too mathematical and too rigorous to engage with most of cognitive science and psychology](https://cogsci.stackexchange.com/a/4807/29), but there are a few connections. I recommend looking at the cstheory question: [What is the complexity class most closely associated with what the human mind can accomplish quickly?](https://cstheory.stackexchange.com/q/5379/1037)

In that question, the author is curious to know which [complexity class](http://en.wikipedia.org/wiki/Complexity_class) most closely resembles what humans can achieve. My favourite [answer](https://cstheory.stackexchange.com/a/5388/1037) discusses the **Tractable Cognition thesis**. For reference, see these papers:

* Iris van Rooij. [The Tractable Cognition thesis](http://staff.science.uva.nl/~szymanik/papers/TractableCognition.pdf). Cognitive Science, 32, pp. 939-984, 2008.
* Iris van Rooij. Parameters that make Cognitive Work Light. [FPT News: Parameterized Complexity Newsletter, June 2009](http://www.mrfellows.net/Newsletters/2009June_FPT_News.pdf).

A specialized part of computational complexity known as [computational learning theory](http://en.wikipedia.org/wiki/Computational_learning_theory) has been particularily notable in trying to make connections to cognitive science, in particular linguists. [Gold's theorem](http://www.lps.uci.edu/~johnsonk/Publications/Johnson.GoldsTheorem.pdf) on the non-learnability of certain families of formal languages was especially relevant in the early days of the [poverty of the stimulus](http://en.wikipedia.org/wiki/Poverty_of_the_stimulus) debate. You can learn more about it in these two questions:

* [Applications of computational learning theory in the cognitive sciences](https://cogsci.stackexchange.com/q/985/29)
* [General mathematical frameworks of language acquisition since Gold](https://linguistics.stackexchange.com/q/1066/33)

Keep in mind, that computational complexity is advanced material and requires a decent mathematical sophistication. However, with difficulty comes insights.


---

