Most relevant explanation: Computational complexity and approximation methods

DOI10.1007/S10472-011-9260-ZMaRDI QIDQ766267zbMATH OpenOpenAlexFDO

Authors Changhe Yuan, Heejin Lim, Michael L. Littman

Publication date 23 March 2012

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10472-011-9260-z

zbMATH Keywords

\(\text{NP}^{\text{PP}}\)-completecomputational complexitylocal searchmost relevant explanationreversible jump MCMC

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Recommendations

• scientific article; zbMATH DE number 3999286
• Complexity of approximation problems
• Complexity Approximation Principle
• scientific article; zbMATH DE number 1206797
• scientific article; zbMATH DE number 3902037
• The complexity of polynomial-time approximation
• scientific article; zbMATH DE number 4057841
• scientific article; zbMATH DE number 1264429
• scientific article; zbMATH DE number 1330032
• Approximation algorithms

Cites work

• Computational Complexity of Probabilistic Turing Machines
• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 1216123 (Why is no real title available?)
• scientific article; zbMATH DE number 2016115 (Why is no real title available?)
• scientific article; zbMATH DE number 2243356 (Why is no real title available?)
• Likelihoodism, Bayesianism, and relational confirmation
• Most relevant explanation in Bayesian networks
• Optimization by simulated annealing
• Reversible jump Markov chain Monte Carlo computation and Bayesian model determination
• The complexity of theorem-proving procedures

Cited in

(5)

• The role of relevance in explanation. I: Irrelevance as statistical independence
• Hierarchical beam search for solving most relevant explanation in Bayesian networks
• Most frugal explanations in Bayesian networks
• Exact algorithms for MRE inference
• Most relevant explanation in Bayesian networks

This page was built for publication: Most relevant explanation: Computational complexity and approximation methods

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