Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

DOI10.1016/S0004-3702(03)00110-3MaRDI QIDQ814531zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Carmel Domshlak, Solomon E. 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

zbMATH Keywords

ComplexityBayes networksProbabilistic reasoningSingly-connected DAGs

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37)

Recommendations

• Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing
• Most probable explanations in Bayesian networks: complexity and tractability
• The complexity of finding \(k\)th most probable explanations in probabilistic networks
• scientific article; zbMATH DE number 1043982
• Reasoning with BKBs -- algorithms and complexity

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1946870 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• scientific article; zbMATH DE number 6472599 (Why is no real title available?)
• A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
• An \(O(|V|^2)\) algorithm for single connectedness
• An algebra of bayesian belief universes for knowledge‐based systems
• Approximating MAPs for belief networks is NP-hard and other theorems
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Finding MAPs for belief networks is NP-hard
• Local conditioning in Bayesian networks
• NP is as easy as detecting unique solutions
• On the hardness of approximate reasoning
• Probabilistic Horn abduction and Bayesian networks
• Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks
• Recursive conditioning
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(6)

• Estimating the probability of meeting a deadline in schedules and plans
• Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing
• Approximate belief updating in max-2-connected Bayes networks is NP-hard
• The complexity of finding \(k\)th most probable explanations in probabilistic networks
• 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

This page was built for publication: Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q814531)