Logic and Complexity in Cognitive Science

This chapter surveys the use of logic and computational complexity theory in cognitive science. We emphasize in particular the role played by logic in bridging the gaps between Marr’s three levels: representation theorems for non-monotonic logics resolve algorithmic/implementation debates, while complexity theory probes the relationship between computational task analysis and algorithms. We argue that the computational perspective allows feedback from empirical results to guide the development of increasingly subtle computational models. We defend this perspective via a survey of the role of logic in several classic problems in cognitive science (the Wason selection task, the frame problem, the connectionism/symbolic systems debate) before looking in more detail at case studies involving quantifier processing and social cognition. In these examples, models developed by Johan van Benthem have been supplemented with complexity analysis to drive successful programs of empirical research.