# Is Bayesian updating computationally unfeasible?

Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be possible to compute the Bayesian probabilities in polynomial time, and the Bayesian update algorithm should also be computable in polynomial time. Unfortunately, this doesn't appear to be the case in general.

Consider the following example: We have some set of all strings $X$ of length $n$, and a one-way function $f$ from $X$ to $Y$. For the Bayesian prior, choose a uniform probability distribution over $X$. Say the string is $x \in X$, but we haven't and won't measure it yet, so we don't know what $x$ is. However, we compute and measure $y = f(x)$. Using standard Bayesian theory, we can figure out what the theoretical Bayesian posterior distribution ought to be. However, by definition, it can't be computed in polynomial time.

What implications does this have for Bayesian theory?

PS: Actual physical agents often aren't all that rational. In fact, most of them can probably be Dutch booked, and their bets would be influenced a lot by the context. Also, many of them seldom update their beliefs based upon contrary evidence. Whatever Bayesianism is, it most certainly is an abstraction.

• A good question, though I would be surprised if anything as computationally difficult as one-way functions was needed to make a Bayesian model of a rational agent in a real environment (that's not to say that such a model wouldn't rely on computationally difficult functions, only that from the point of view of modelling real agents 1-way functions etc. seem to be quite contrived). – Marcin Kotowski Oct 8 '11 at 15:51