В целом изучаются два типа «сложности». Обычно, когда люди говорят о «сложности», особенно в Интернете, они имеют в виду сложность стиля Института Санта-Фе. Это расплывчатая и плохо определенная концепция, которая боролась в течение ряда лет, не добившись существенного прогресса. Он использует красивые слова, но еще не дал никаких реальных результатов. Я не буду обсуждать это больше в этом ответе.
Другой тип сложности — это теория вычислительной сложности , изучаемая теоретической информатикой. В общем, эта область слишком математическая и слишком строгая, чтобы взаимодействовать с большей частью когнитивной науки и психологии , но есть несколько связей. Я рекомендую взглянуть на вопрос из теории: какой класс сложности наиболее тесно связан с тем, что человеческий разум может сделать быстро?
В этом вопросе автору любопытно узнать, какой класс сложности больше всего напоминает то, чего могут достичь люди. Мой любимый ответ обсуждает тезис Tractable Cognition . Для справки см. эти документы:
Специализированная часть вычислительной сложности, известная как вычислительная теория обучения , была особенно примечательна в попытках установить связь с когнитивной наукой, в частности с лингвистами. Теорема Голда о невозможности изучения некоторых семейств формальных языков была особенно актуальна в первые дни скудости дебатов о стимулах. Вы можете узнать больше об этом в этих двух вопросах:
Имейте в виду, что вычислительная сложность — это продвинутый материал, требующий приличной математической сложности. Однако с трудом приходят озарения.