Dempster's rule of combination is #P-complete

摘要

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.