On the Complexity of Bayesian Signal Processing

Yi Liu

We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This hardness n…