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. (shrink)

Mental model ascription – also called mindreading – is the process of inferring the mental states of others, which happens as a matter of course in social interactions. But although ubiquitous, mindreading is presumably a highly variable process: people mindread to different extents and with different results. We hypothesize that human mindreading ability relies on a large number of personal and contextual features: the inherent abilities of specific individuals, their current physical and mental states, their knowledge of the domain of (...) discourse, their familiarity with the interlocutor, the risks associated with an incorrect assessment of intent, and so on. This paper presents a theory of mindreading that models diverse artificial intelligent agents using an inventory of parameters and value sets that represent traits of humans and features of discourse contexts. Examples are drawn from Maryland Virtual Patient, a prototype system that will permit medical trainees to diagnose and treat cognitively modeled virtual patients with the optional assistance of a virtual tutor. Since real patients vary greatly with respect to physiological and cognitive features, so must a society of virtual patients. Modeling such variation is one of the goals of the overall OntoAgent program of research and development. (shrink)