Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis

ISBN-13: 9781107043992 / Angielski / Twarda / 2019 / 374 str.

Iris Van Rooij; Mark Blokpoel; Johan Kwisthout

Opis

Provides an accessible introduction to computational complexity analysis and its application to questions of intractability in cognitive science.

Recenzje

'Current theories in cognitive science think of mental processes as computational, but they rarely provide rigorous analysis of the relevant computations. Cognition and Intractability applies computational complexity theory to the kinds of inference that are important for human thinking. The results are mathematically elegant, pedagogically helpful, and very useful for understanding the kinds of computational processes that minds use.' Paul Thagard, University of Waterloo, Canada

Spis treści

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.