Return to search

Tractable cognition : complexity theory in cognitive psychology

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. / Graduate
Date27 April 2017
Creatorsvan Rooij, Iris
ContributorsKadlec, Helena, Stege, Ulrike
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
RightsAvailable to the World Wide Web

Page generated in 0.0381 seconds