Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard

Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard. Dagum, P. and Luby, M. Artif Intell, 60(1):141–153, 1993.
doi abstract bibtex

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 subseteq P. We present our proof and explore the implications of the result.

@Article{dagum93approximating,
  author    = {Paul Dagum and Michael Luby},
  title     = {Approximating Probabilistic Inference in {Bayesian} Belief Networks is {NP}-Hard},
  journal   = {Artif Intell},
  year      = {1993},
  volume    = {60},
  number    = {1},
  pages     = {141--153},
  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 subseteq P. We present our proof and explore the implications of the result.},
  doi       = {10.1016/0004-3702(93)90036-B},
  keywords  = {Bayesian networks; inference; complexity; NP-hard;},
  owner     = {Sebastian},
  timestamp = {2017.06.07},
}

Downloads: 0