# Tractability and the computational mind

In Mark Sprevak & Matteo Colombo (eds.),

*The Routledge Handbook of the Computational Mind*. Oxford, UK: pp. 339-353 (2018)**Abstract**

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to be practically computable.
Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability.
We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition.

**Keywords**

No keywords specified (fix it)

**Categories**

**PhilPapers/Archive ID**

RINTAT

**Revision history**

Archival date: 2019-02-06

View upload history

View upload history

References found in this work BETA

No references found.

Citations of this work BETA

No citations found.

**Added to PP index**

2019-02-06

**Total downloads**

11 ( #36,256 of 37,117 )

**Recent downloads (6 months)**

11 ( #24,973 of 37,117 )

How can I increase my downloads?

**Monthly downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks to external links.*