Approximating probabilistic inference in Bayesian belief networks is NP- hard (Q685336): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: DBLP publication ID (P1635): journals/ai/DagumL93, #quickstatements; #temporary_batch_1731462974821 |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0004-3702(93)90036-b / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1999432334 / rank | |||
Normal rank | |||
Property / DBLP publication ID | |||
Property / DBLP publication ID: journals/ai/DagumL93 / rank | |||
Normal rank |
Latest revision as of 03:01, 13 November 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximating probabilistic inference in Bayesian belief networks is NP- hard |
scientific article |
Statements
Approximating probabilistic inference in Bayesian belief networks is NP- hard (English)
0 references
17 February 1994
0 references
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\).
0 references
conditional probabilities
0 references
belief networks
0 references
NP-complete
0 references
upper bound
0 references
0 references
0 references