The theory of computational complexity can be used to analyse cognitive models for their computational resource demands. Models that assume an unrealistic amount of computational resources are computationally intractable and therefore at worst psychologically implausible and at best theoretically problematic.

Using the tools and techniques from both classical complexity theory and parametrized complexity theory new model variants can be built that may yet meet the computational tractability constraint.

• van Rooij, I. (2008). The Tractable Cognition thesis. Cognitive Science, 32, 939-984. [prepublication draft in pdf]
• van Rooij, I., Evans, P., Müller, M., Gedge, J. & Wareham, T. (2008). Identifying sources of intractability in cognitive models: An illustration using analogical structure mapping. Proceedings of the 30th Annual Meeting of the Cognitive Science Society. [paper in pdf and supplementary material]
• van Rooij, I., & Wareham, T. (2008). Parameterized complexity in cognitive modeling: Foundations, applications and opportunities. Computer Journal, 51(3), 385-404. [preprint]
• Wareham, T., van Rooij, I., & Müller, M. (2008). Computational complexity analysis can help, but first we need a theory. Behavioral and Brain Sciences, 51(4), 399-400. [prepublication draft in html].
• Hamilton, M., Müller, M., van Rooij, I., & Wareham, T. (2007). Approximating solution structure. In E. Demaine, G. Z. Gutin, D. Marx, and U. Stege (Eds.), Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings (Nr. 07281). Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany. [pdf]
• van Rooij, I., Stege, U., & Kadlec, H. (2005). Sources of complexity in subset choice. Journal of Mathematical Psychology, 49(2), 160-187. [pdf]
• van Rooij, I. (2003). Tractable cognition: Complexity theory in cognitive psychology. PhD thesis, University of Victoria, Canada. [pdf] [abstract]
  

The Traveling Salesperson Problem (TSP) is a computationally intractable (NP-hard) combinatorial optimization problem. Nonetheless people seem to perform remarkably well on the task of finding (close to) shortest tours visiting points in the plane.

It is conjectured that the psychological study of how humans "solve" the TSP may not only provide ideas for the design of smart heuristics in computer science and operations research, but also that it may lead to basic insights about human intelligence and, in particular, how people deal with the complexity inherent in their life world.

• van Rooij, I., Schactman, A., Kadlec, H., & Stege, U. (2006). Perceptual or analytical processing? Evidence from children’s and adult’s performance on the Euclidean Traveling Salesperson problem. Journal of Problem Solving, 1(1), 44-73. [pdf]
• van Rooij, I., Stege, U., & Schactman, A. (2003). Convex hull and tour crossings in the Euclidean Traveling Salesperson problem: Implications for human performance studies. Memory & Cognition, 31(2), 215-220. [pdf]
• Tak, S., Plaisier, M., & van Rooij, I. (2008). Some tours are more equal than others: The convex-hull model revisited with lessons for testing models of the Traveling Salesperson Problem. Journal of Problem Solving, 2, 4-28. [paper in pdf and software & illustrations]

According to the view of Embodied Embedded Cognition (EEC), cognition is not restricted to internal information-processing, but it extends also beyond the brain into the body and the world.

This view presents a potential way to deal with some problems that have plagued the classical internalist cognitivist approach, such as the grounding problem, the frame-problem and the problem of (the computational complexity of) common-sense belief fixation.

• Haselager, W.F.G., van Dijk, J., & van Rooij, I. (2008). A lazy brain? Embodied embedded cognition and cognitive neuroscience. In P. Calvo and T. Gomila (Eds.), Handbook of Cognitive Science: An Embodied Approach (pp. 273-290). Oxford: Elsevier. [pdf]
• van Dijk, J., Kerkhofs, R., van Rooij, I., & Haselager, P. (2008). Can there be such a thing as embodied embedded cognitive neuroscience? Theory & Psychology, 13(8), 297-316. [prepublication draft in pdf]
• van Rooij, I., Haselager, W.F.G., & Bekkering, H. (2008). Goals are not implied by actions, but inferred from actions and contexts. Behavioral and Brain Sciences, 31, 38-39. [prepublication draft in html]
• Haselager, W. F. G., Bongers, R. M., & van Rooij, I. (2003). Cognitive science, representations and dynamical systems theory. In W. Tschacher and J-P. Dauwalder (Eds.), The dynamical systems approach to cognition (pp. 229- 242). Singapore: World Scientific. [prepublication draft in pdf]
• van Rooij, I., Bongers, R. M., & Haselager, W. F. G. (2002). A non-representational approach to imagined action. Cognitive Science, 26(3), 345-375. [pdf]

See also: Pim Haselager's publications and EEC page.