Approximating probabilistic inference in Bayesian belief networks is NP-hard

TLDR

Exact computation of conditional probabilities in belief networks is NP‑hard, and although some special cases allow polynomial‑time approximate inference, the AI community has generally assumed polynomial complexity for approximate algorithms. The authors aim to analyze the complexity of approximate probabilistic inference in belief networks. They construct a proof showing that a polynomial‑time relative approximation algorithm for key problem classes would imply NP ⊆ P, and they discuss the implications. They conclude that approximating conditional probabilities in general belief networks is NP‑hard, just as exact inference is.

Abstract

It is known that exact computation of conditional probabilities in belief networks is NP-hard. Many investigators in the AI community have tacitly assumed that algorithms for performing approximate inference with belief networks are of polynomial complexity. Indeed, special cases of approximate inference can be performed in time polynomial in the input size. However, we have discovered that the general problem of approximating conditional probabilities with belief networks, like exact inference, resides in the NP-hard complexity class. We develop a complexity analysis to elucidate the difficulty of approximate probabilistic inference. More specifically, we show that the existence of a polynomial-time relative approximation algorithm for major classes of problem instances implies that NP ⊆ P. We present our proof and explore the implications of the result.