Approximating probabilistic inference in Bayesian belief networks is NP- hard (Q685336)

Using the reduction method of \textit{G. F. Cooper} [The computational complexity of probabilistic inference using Bayesian belief networks, Artif. Intell. 42, 393-405 (1990; Zbl 0717.68080)], the authors show that the problem of approximating conditional probabilities with belief networks is NP-complete. In particular, the problem is shown to depend on the ration \(\lambda\) of a priori bounds given for the probabilities. If all probabilities between \(n\) events are in an interval \([1,u]\subset[0,1]\) and \(\lambda=u/1<1+(c\log n)/n\) then the problem is known to have a polynomial time solution. If \(\lambda\geq e^{cn}\) then the problem is hard. The problem therefore is to find a best and a practical upper bound for \(\lambda\).