Tractability and the computational mind

Computational complexity theory, or in other words, the theory of tractability and intractability, is defined in terms of limit behavior. This chapter overviews some interesting empirical evidence corroborating computational and logical predictions inspired by tractability considerations. It focuses on the distinction between tractable and intractable problems and takes the computational perspective on cognition. The chapter gives a personal selection of the computational approach to study different aspects of cognition, namely Boolean categorization, semantic processing, and social reasoning. It shows several cases in which the P-Cognition Thesis fails but the Fixed-parameter Tractability Thesis comes to the rescue, while in one case of social reasoning, apparent levels of cognitive difficulty do not line up with levels of computational. The chapter reviews some interesting puzzles and games in which it is useful for people to reason about one another's knowledge, beliefs, and intentions and checks the relevance of the P-Cognition Thesis and the Fixed-parameter Tractability Thesis for these tasks.