Dempster's rule of combination is {\#}P-complete

DOI10.1016/0004-3702(90)90103-7zbMath0717.68048OpenAlexW2132996183MaRDI QIDQ2638783

Pekka Orponen

Publication date: 1990

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10138/243069

zbMATH Keywords

uncertain informationDempster-Shafer theory of evidenceDempster's rule of combinationcomplexity of Dempster-Shafer computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (16)

Phase transitions of PP-complete satisfiability problems ⋮ Graph decompositions and tree automata in reasoning with uncertainty ⋮ Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects ⋮ Measures of uncertainty in expert systems ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Monte Carlo and quasi-Monte Carlo methods for Dempster's rule of combination ⋮ On the hardness of approximate reasoning ⋮ Depth-bounded belief functions ⋮ Approximating the combination of belief functions using the fast Möbius transform in a coarsened frame. ⋮ Resource bounded and anytime approximation of belief function computations. ⋮ A logic-based analysis of Dempster-Shafer theory ⋮ On the complexity of belief network synthesis and refinement ⋮ Approximation algorithms and decision making in the Dempster-Shafer theory of evidence---an empirical study ⋮ Unnamed Item ⋮ Approximate Inference in Directed Evidential Networks with Conditional Belief Functions Using the Monte Carlo Algorithm ⋮ An evidential similarity-based regression method for the prediction of equipment remaining useful life in presence of incomplete degradation trajectories

Cites Work

• The complexity of computing the permanent
• A logic-based analysis of Dempster-Shafer theory
• Implementing Dempster's rule for hierarchical evidence
• The Complexity of Enumeration and Reliability Problems
• A method for managing evidential reasoning in a hierarchical hypothesis space: a retrospective
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Dempster's rule of combination is {\#}P-complete