|
- It is known that exact inference in Bayesian Networks is NP-Hard with respect to the network size.
- Cooper, G.F. (1990). The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence, 42, 393-405
- Approximate Bayesian Network inference scales well with network size, but is NP-Hard with respect to the hard-bound accuracy of the estimates.
- Dagum P., & Luby, M. (1993). Approximating probabilistic inference in Bayesian belief networks is NP-Hard. Artificial Intelligence, 60 141-153.
|
