Enhancing methodological rigor for computational cognitive science: Computational complexity. Cognitive Science Conference

Complexity analysis provides a measure of how well the com-putations being performed by a cognitive model are supported by the constraints of biological computing. We argue that research in computational cognitive science will be greatly aided by treating computational complexity as a primary is-sue on the same order of importance as significance analysis in experimental work. In this paper, we give a brief review of computational complexity and its application in computer science. We then show how it can be applied to incorporate biological constraints abstractly into computational cognitive science research, even in the presence of massive uncertainty about the underlying neuroscience. To ground this discussion of complexity, examples are drawn from two recent pieces of work: Xu and Tenenbaum’s work applying Bayesian inference to word learning (Xu & Tenenbaum, 2007) and Forbus and Hinrich’s work on the construction of a large-scale analogica