Cognition and Intractability

Iris van Rooij is a psychologist and cognitive scientist based at the Donders Institute for Brain, Cognition and Behaviour and the School for Psychology and Artificial Intelligence at Radboud Universiteit Nijmegen, the Netherlands. Mark Blokpoel is a computational cognitive scientist at the Donders Institute for Brain, Cognition and Behaviour at Radboud Universiteit Nijmegen, the Netherlands. Johan Kwisthout is a computer scientist at the Donders Institute for Brain, Cognition and Behaviour and the School for Psychology and Artificial Intelligence at Radboud Universiteit Nijmegen, the Netherlands. Todd Wareham is a computer scientist in the Department of Computer Science at Memorial University of Newfoundland, Canada.

• Part I. Introduction: 1. Introduction; Part II. Concepts and Techniques: 2. Polynomial versus exponential time; 3. Polynomial-time reductions; 4. Classical complexity classes; 5. Fixed-parameter tractable time; 6. Parameterized reductions; 7. Parameterized complexity classes; Part III. Reflections and Elaborations: 8. Dealing with intractability; 9. Replies to common objections; Part IV. Applications: 10. Coherence as constraint satisfaction; 11. Analogy as structure mapping; 12. Communication as Bayesian inference.

'Computational complexity has long been the elephant in the room in cognitive science. Researchers, including myself, blithely propose models that, if taken literally, would imply the brain can solve computational problems that are known to be intractable. This excellent introduction to both the technical results and their cognitive relevance should alert students and researchers to these pressing questions.' Nick Chater, University of Warwick