Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard. Dagum, P. & 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
{"_id":{"_str":"534279620e946d920a0014fe"},"__v":1,"authorIDs":[],"author_short":["Dagum, P.","Luby, M."],"bibbaseid":"dagum-luby-approximatingprobabilisticinferenceinbayesianbeliefnetworksisnphard-1993","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Paul"],"propositions":[],"lastnames":["Dagum"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Luby"],"suffixes":[]}],"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","bibtex":"@Article{dagum93approximating,\n author = {Paul Dagum and Michael Luby},\n title = {Approximating Probabilistic Inference in {Bayesian} Belief Networks is {NP}-Hard},\n journal = {Artif Intell},\n year = {1993},\n volume = {60},\n number = {1},\n pages = {141--153},\n 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.},\n doi = {10.1016/0004-3702(93)90036-B},\n keywords = {Bayesian networks; inference; complexity; NP-hard;},\n owner = {Sebastian},\n timestamp = {2017.06.07},\n}\n\n","author_short":["Dagum, P.","Luby, M."],"key":"dagum93approximating","id":"dagum93approximating","bibbaseid":"dagum-luby-approximatingprobabilisticinferenceinbayesianbeliefnetworksisnphard-1993","role":"author","urls":{},"keyword":["Bayesian networks; inference; complexity; NP-hard;"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","downloads":0,"keywords":["bayesian networks; inference; complexity; np-hard;"],"search_terms":["approximating","probabilistic","inference","bayesian","belief","networks","hard","dagum","luby"],"title":"Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard","year":1993,"dataSources":["C5FtkvWWggFfMJTFX"]}