Approximating probabilistic inference in Bayesian belief networks is NP-hard

1993/03/01 by Paul Dagum, Michael Luby · 775 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Approximate inference #Artificial intelligence #Bayesian Modeling and Causal Inference #Bayesian inference #Bayesian network #Bayesian probability #Class (philosophy) #Complexity class #Computational complexity theory #Computer science #Discrete mathematics #Graphical model #Inference #Machine Learning and Algorithms #Mathematics #Polynomial #Probabilistic analysis of algorithms #Probabilistic logic #Theoretical computer science #Time complexity

paper · doi:10.1016/0004-3702(93)90036-b

published in Artificial Intelligence 60(1), 141-153 (Elsevier BV)

openalex publication_date 1993/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Cited by

• Generative Model for Heterogeneous Inference
• Exact MAP inference in general higher-order graphical models using linear programming
• Correlated Equilibria for Approximate Variational Inference in MRFs
• On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions
• Generalization in anti-causal learning
• Plausibility and probability in deductive reasoning
• Bayesian Intractability Is Not an Ailment That Approximation Can Cure
• On the Complexity of Solving Markov Decision Problems
• Determinantal point processes for machine learning
• Efficient Search-Based Inference for Noisy-OR Belief Networks:\n TopEpsilon
• Approximating MAP using Local Search
• DODO: Causal Structure Learning with Budgeted Interventions
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
• Belief Updating by Enumerating High-Probability Independence-Based Assignments
• Mathematical Programs for Belief Propagation and Consensus
• Iterative Join-Graph Propagation
• State-space Abstraction for Anytime Evaluation of Probabilistic Networks
• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• A high-performance analog Max-SAT solver and its application to Ramsey numbers
• Branch-and-bound method for calculating Viterbi path in triplet Markov models
• Bayesian Tensor Network with Polynomial Complexity for Probabilistic Machine Learning
• Marginal Densities, Factor Graph Duality, and High-Temperature Series Expansions
• Computing Upper and Lower Bounds on Likelihoods in Intractable Networks
• An Importance Sampling Algorithm Based on Evidence Pre-propagation
• Studies in Lower Bounding Probabilities of Evidence using the Markov Inequality
• Monte Carlo Inference via Greedy Importance Sampling
• Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
• Sensitivities: An Alternative to Conditional Probabilities for Bayesian Belief Networks
• Sample-and-Accumulate Algorithms for Belief Updating in Bayes Networks
• Real Time Estimation of Bayesian Networks
• Optimal Monte Carlo Estimation of Belief Network Inference
• Polynomial-Time Relational Probabilistic Inference in Open Universes
• On the Hardness of Approximating Distributions with Tractable Probabilistic Models
• Semantically Enhanced Dynamic Bayesian Network for Detecting Sepsis Mortality Risk in ICU Patients with Infection
• Why Heuristics Work
• Learning Bayesian Nets that Perform Well
• Using Deep Neural Network Approximate Bayesian Network
• Computational Complexity Reduction for BN2O Networks Using Similarity of States
• Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test
• Probabilistic and Causal Satisfiability: Constraining the Model
• Footprints Sticking Out of the Sand. Part 2: Children's Bayesian Priors for Shape and Lighting Direction
• Bayesian Networks for Data Mining
• An optimal approximation algorithm for Bayesian inference
• A Structurally and Temporally Extended Bayesian Belief Network Model: Definitions, Properties, and Modeling Techniques
• Bounding probabilistic relationships in Bayesian networks using qualitative influences: methods and applications
• Evaluation of Bayesian networks with flexible state-space abstraction methods
• Stochastic Simulation Algorithms for Dynamic Probabilistic Networks
• Speedup Chip Yield Analysis by Improved Quantum Bayesian Inference
• Bayesian network [wikipedia]
• Bayesian networks in neuroscience: a survey. [europepmc]
• A Factor Graph Approach to Automated GO Annotation. [europepmc]
• The blessing of Dimensionality: Feature Selection outperforms functional connectivity-based feature transformation to classify ADHD subjects from EEG patterns of phase synchronisation. [europepmc]
• Biological plausibility and stochasticity in scalable VO 2 active memristor neurons. [europepmc]
• A continuous-time MaxSAT solver with high analog performance. [europepmc]
• Uncertainty and computational complexity. [europepmc]
• Polynomial-Time Algorithm for Learning Optimal BFS-Consistent Dynamic Bayesian Networks. [europepmc]
• Structure Learning of Bayesian Network Based on Adaptive Thresholding. [europepmc]
• Universal Target Learning: An Efficient and Effective Technique for Semi-Naive Bayesian Learning. [europepmc]
• Dynamic Bayesian Networks for Integrating Multi-omics Time Series Microbiome Data. [europepmc]
• Gated recurrence enables simple and accurate sequence prediction in stochastic, changing, and structured environments. [europepmc]
• Does supply chain matter for environmental firm performance: mediating role of financial development in China [europepmc]