Skip to content
Register Sign in Wishlist

Cognition and Intractability
A Guide to Classical and Parameterized Complexity Analysis


  • Date Published: April 2019
  • availability: In stock
  • format: Hardback
  • isbn: 9781107043992

£ 84.99

Add to cart Add to wishlist

Other available formats:
Paperback, eBook

Looking for an inspection copy?

This title is not currently available on inspection

Product filter button
About the Authors
  • Intractability is a growing concern across the cognitive sciences: while many models of cognition can describe and predict human behavior in the lab, it remains unclear how these models can scale to situations of real-world complexity. Cognition and Intractability is the first book to provide an accessible introduction to computational complexity analysis and its application to questions of intractability in cognitive science. Covering both classical and parameterized complexity analysis, it introduces the mathematical concepts and proof techniques that can be used to test one's intuition of (in)tractability. It also describes how these tools can be applied to cognitive modeling to deal with intractability, and its ramifications, in a systematic way. Aimed at students and researchers in philosophy, cognitive neuroscience, psychology, artificial intelligence, and linguistics who want to build a firm understanding of intractability and its implications in their modeling work, it is an ideal resource for teaching or self-study.

    • The first book to describe how classical and parameterized complexity analysis can be applied to cognitive modeling
    • Provides a rigorous yet accessible introduction to the conceptual and mathematical foundations of intractability
    • Illustrates various complexity-theoretic proof techniques that can be used by cognitive researchers as part of their theoretical toolkit
    Read more

    Reviews & endorsements

    '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

    'Cognitive science and algorithms and complexity research are converging: mathematically speaking, there is a revolution in the cognitive models and tools available, while multivariate (parameterized) algorithmics are essential to understanding them. As our growing awareness of how natural systems algorithmically process information leads to intellectual flows in both directions, the insights in this book are highly useful to students and researchers in both fields.' Michael Fellows, University of Bergen, Norway

    '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

    See more reviews

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity


    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?


    Product details

    • Date Published: April 2019
    • format: Hardback
    • isbn: 9781107043992
    • length: 374 pages
    • dimensions: 234 x 157 x 24 mm
    • weight: 0.65kg
    • contains: 67 b/w illus. 19 tables
    • availability: In stock
  • Table of Contents

    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.

  • Authors

    Iris van Rooij, Radboud Universiteit Nijmegen
    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, Radboud Universiteit Nijmegen
    Mark Blokpoel is a computational cognitive scientist at the Donders Institute for Brain, Cognition and Behaviour at Radboud Universiteit Nijmegen, the Netherlands.

    Johan Kwisthout, Radboud Universiteit Nijmegen
    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, Memorial University of Newfoundland
    Todd Wareham is a computer scientist in the Department of Computer Science at Memorial University of Newfoundland, Canada.

Sign In

Please sign in to access your account


Not already registered? Create an account now. ×

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner Please see the permission section of the catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.


Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

Please fill in the required fields in your feedback submission.