van Rooij, I. (2003). Tractable Cognition: Complexity Theory in Cognitive Psychology. PhD thesis, University of Victoria, Canada. [fulltext]
Abstract:
This research investigates the import and utility of computational
complexity theory in cognitive psychology. A common conception in cognitive
psychology is that a cognitive system is to be understood in terms of the
function that it computes. The recognition that cognitive systems¾being
physical systems¾are
limited in space and time has led to the Tractable Cognition thesis:
only tractably computable functions describe cognitive systems. This
dissertation considers two possible formalizations of the Tractable Cognition
thesis. The first, called the P-Cognition thesis, defines tractability as polynomial-time
computability and is the dominant view in cognitive science today. The
second, called the FPT-Cognition thesis, is proposed by the author and defines
tractability as fixed-parameter tractability for some “small” input
parameters. The FPT-Cognition thesis is shown to provide a useful relaxation of
the P-Cognition thesis. To illustrate how the FPT-Cognition thesis can be put
into practice, a set of simple but powerful tools for complexity analyses is
introduced. These tools are then used to analyze the complexity of existing
cognitive theories in the domains of coherence reasoning, subset choice,
binary-cue prediction and visual matching. Using psychologically motivated
examples, a sufficiently diverse set of functions, and simple proof techniques,
this manuscript aims to make the theory of classical and parameterized
complexity tangible for cognitive psychologists. With the tools of complexity
theory in hand a cognitive psychologist can study the a priori
feasibility of cognitive theories and discover interesting and potentially
useful cognitive parameters. Possible criticisms of the Tractable Cognition
thesis are discussed and existing misconceptions are clarified.