Bayesian Intractability Is Not an Ailment That Approximation Can Cure

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


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



    Upload a copy of this work     Papers currently archived: 92,075

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

73 (#226,039)

6 months
13 (#195,290)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Iris van Rooij
Radboud University Nijmegen

Citations of this work

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.
Bayesian Cognitive Science, Monopoly, and Neglected Frameworks.Matteo Colombo & Stephan Hartmann - 2015 - British Journal for the Philosophy of Science 68 (2):451–484.
Subjective Probability as Sampling Propensity.Thomas Icard - 2016 - Review of Philosophy and Psychology 7 (4):863-903.

View all 24 citations / Add more citations