Computational complexity analysis for cognitive scientists


Many computational- or rational-level models of cognition postulate computations that appear to be computationally intractable (e.g., NP-hard or worse). Formally, this means that the postulated computations consume an exponential amount of time. Informally, this means that the postulated computations do not scale in any obvious way to explain how the modeled cognitive capacities can operate in the real world outside the lab. This problem of intractability is quite common in cognitive science. It is observed in practically all domains of cognition, including, for instance, perception, language, reasoning, categorization, decision-making, and motor planning. It is also not specific to any particular class of models, as it can arise for symbolic, connectionist, probabilistic (e.g. Bayesian), dynamical, logic-based, and even heuristic models of cognition.

Back to Table of Contents