Cognitive Science 35 (5):779-784 (2011)

Iris van Rooij
Radboud University Nijmegen
Bayesian models are often criticized for postulating computations that are computationally intractable (e.g., NP-hard) and therefore implausibly performed by our resource-bounded minds/brains. Our letter is motivated by the observation that Bayesian modelers have been claiming that they can counter this charge of “intractability” by proposing that Bayesian computations can be tractably approximated. We would like to make the cognitive science community aware of the problematic nature of such claims. We cite mathematical proofs from the computer science literature that show intractable Bayesian computations, such as postulated in existing Bayesian models, cannot be tractably approximated. This does not mean that human brains do not (or cannot) implement the type of algorithms that Bayesian modelers are advancing, but it does mean that proposing that they do by itself does nothing to parry the charge of intractability, because the postulated algorithms are as intractable (i.e., require exponential time) as the computations they try to approximate. Besides our negative message for the community, our letter also makes a positive contribution by referring to a methodology that Bayesian modelers can use to try and parry the charge of intractability in a mathematically sound way
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1111/j.1551-6709.2011.01182.x
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 68,916
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Simple Heuristics That Make Us Smart.Gerd Gigerenzer, Peter M. Todd & A. B. C. Research Group - 1999 - New York, NY, USA: Oxford University Press USA.
Probabilistic Models of Cognition: Conceptual Foundations.Nick Chater & Alan Yuille - 2006 - Trends in Cognitive Sciences 10 (7):287-291.
Vision as Bayesian Inference: Analysis by Synthesis?Alan Yuille & Daniel Kersten - 2006 - Trends in Cognitive Sciences 10 (7):301-308.

View all 18 references / Add more references

Citations of this work BETA

Being Realist About Bayes, and the Predictive Processing Theory of Mind.Matteo Colombo, Lee Elkin & Stephan Hartmann - 2021 - British Journal for the Philosophy of Science 72 (1):185-220.
Subjective Probability as Sampling Propensity.Thomas Icard - 2016 - Review of Philosophy and Psychology 7 (4):863-903.
Bayes, Bounds, and Rational Analysis.Thomas F. Icard - 2018 - Philosophy of Science 85 (1):79-101.

View all 18 citations / Add more citations

Similar books and articles


Added to PP index

Total views
59 ( #190,965 of 2,497,803 )

Recent downloads (6 months)
4 ( #171,501 of 2,497,803 )

How can I increase my downloads?


My notes