Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
From MaRDI portal
Publication:814531
DOI10.1016/S0004-3702(03)00110-3zbMath1082.68837OpenAlexW2029891923WikidataQ57518782 ScholiaQ57518782MaRDI QIDQ814531
Carmel Domshlak, Solomon Eyal Shimony
Publication date: 7 February 2006
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0004-3702(03)00110-3
Related Items (4)
Approximate belief updating in max-2-connected Bayes networks is NP-hard ⋮ Approximate inference in Bayesian networks: parameterized complexity results ⋮ A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem ⋮ Estimating the probability of meeting a deadline in schedules and plans
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating probabilistic inference in Bayesian belief networks is NP- hard
- NP is as easy as detecting unique solutions
- Approximating MAPs for belief networks is NP-hard and other theorems
- Probabilistic Horn abduction and Bayesian networks
- Finding MAPs for belief networks is NP-hard
- Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks
- An \(O(|V|^2)\) algorithm for single connectedness
- The computational complexity of probabilistic inference using Bayesian belief networks
- On the hardness of approximate reasoning
- Local conditioning in Bayesian networks
- A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
- An algebra of bayesian belief universes for knowledge‐based systems
- Recursive conditioning
This page was built for publication: Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
