Thesis (Ph.D.)--University of Victoria (Canada), 2003
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 <italic>Tractable Cognition thesis </italic>: 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 <italic> polynomial-time computability</italic> 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 <italic>fixed parameter tractability </italic> 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 <italic>a priori</italic> 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
