Dempster's rule of combination is #P-complete

Artificial IntelligencePublished 1 July 1990Open access

Pekka Orponen

Citations106

TL;DR

It is proved that, given as input a set of tables representing basic probability assignments m 1, …, m n over a frame of discernment Θ, and a set A ⊆ Θ , the problem of computing the combined basic probability value (m 1 … ⊕ m n )(A) is # P -complete.

Abstract

We consider the complexity of combining bodies of evidence according to the rules of the Dempster-Shafer theory of evidence. We prove that, given as input a set of tables representing basic probability assignments m1, …, mn over a frame of discernment Θ, and a set A ⊆ Θ, the problem of computing the combined basic probability value (m1 ⊕ … ⊕ mn)(A) is #P-complete. As a corollary, we obtain that while the simple belief, plausibility, and commonality values Bel(A), Pl(A), and Q(A) can be computed in polynomial time, the problems of computing the combinations (Bel1 ⊕ … ⊕ Beln(A), (Pl1 ⊕ … ⊕ Pln)(A), and (Q1 ⊕ … ⊕ Qn)(A) are #P-complete.

Keywords

Computer Science

Theoretical Computer ScienceThe complexity of computing the permanent

2,759 Citations1979Leslie G. Valiant

It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations.

SIAM Journal on ComputingThe Complexity of Enumeration and Reliability Problems

2,086 Citations1979Leslie G. Valiant

For a large number of natural counting problems for which there was no previous indication of intractability, that they belong to the class of computationally eqivalent counting problems that are at least as difficult as the NP-complete problems.

Artificial IntelligenceA method for managing evidential reasoning in a hierarchical hypothesis space

401 Citations1985Jean Gordon, Edward H. Shortliffe

This paper describes the central elements of the Dempster–Shafer (D-S) theory of evidence and demonstrates the relevance of the D-S theory to a familiar expert-system domain, namely the bacterial-organism identification problem that lies at the heart of the mycin system.

Studies in fuzziness and soft computingComputational Methods for A Mathematical Theory of Evidence

393 Citations2008Jeffrey A. Barnett

This paper has two objectives: first, to introduce one such scheme developed by Arthur Dempster and Glen Shafer, to a wider audience, and to present results that can reduce the complexity of this scheme from exponential to linear.

Artificial IntelligenceImplementing Dempster's rule for hierarchical evidence

285 Citations1987Glenn Shafer, Roger Logan

This article gives an algorithm for the exact implementation of Dempster’s rule in the case of hierarchical evidence, which is computationally efficient, and makes the approximation suggested by Gordon and Shortliffe unnecessary.

IEEE ExpertPropagating Belief Functions with Local Computations

236 Citations1986Prakash P. Shenoy, Glenn Shafer

A way to propagate belief functions in certain kinds of trees using only local computations, which generalizes the computational scheme proposed by Pearl5 for Bayesian causal trees and describes qualitative Markov trees.

Morgan Kaufmann Publishers Inc. eBooksThe Dempster-Shafer theory of evidence

164 Citations1990Jill Gordon, Edward H. Shortliffe

The advantage of the Dempster-Shafer theory over previous approaches is its ability to model the narrowing of the hypothesis set with the accumulation of evidence, a process that characterizes diagnostic reasoning in medicine and expert reasoning in general.

Machine intelligence and pattern recognitionHandling Uncertain Information: A Review of Numeric and Non-numeric Methods

79 Citations1986Raj Bhatnagar, Laveen N. Kanal

Probability Theory, Shafer's Evidence Theory, Zadeh's Possibility Theory, Cohen's Theory of Endorsements and the non-monotonic logics are examined for handling uncertainty of information.

IEEE Transactions on Systems Man and CyberneticsPerspectives on imperfect information processing

67 Citations1987H.E. Stephanou, Andrew P. Sage

It is argued that many applications of expert-system and decision-support-system technologies will require an appropriate blend of the features of each of these technologies, and major approaches for the representation of imperfect knowledge and their use in approximate reasoning algorithms for knowledge support systems are described.

International Journal of Approximate ReasoningA logic-based analysis of Dempster-Shafer theory

60 Citations1990Gregory Provan

It is shown that the disjunction of minimal support clauses for a clause $i$ with respect to a set of propositional clauses, is a symbolic representation of the Dempster Shafer Belief function for $\Sigma_{i}$.