We consider in this chapter the computational complexity of probabilistic inference. We also provide some reductions of probabilistic inference to well known problems, allowing us to benefit from specialized algorithms that have been developed for these problems.

Introduction

In previous chapters, we discussed algorithms for answering three types of queries with respect to a Bayesian network that induces a distribution Pr(X). In particular, given some evidence e we discussed algorithms for computing:

• The probability of evidence e, Pr(e) (see Chapters 6–8)

• The MPE probability for evidence e, MPEP (e) (see Chapter 10)

• The MAP probability for variables Q and evidence e, MAPP (Q, e) (see Chapter 10).

In this chapter, we consider the complexity of three decision problems that correspond to these queries. In particular, given a number p, we consider the following problems:

• D-PR: Is Pr(e) > p?

• D-MPE: Is there a network instantiation x such that Pr(x, e) > p?

• D-MAP: Given variables Q ⊆ X, is there an instantiation q such that Pr(q, e) > p?

We also consider a fourth decision problem that includes D-PR as a special case:

• D-MAR: Given variables Q ⊆ X and instantiation q, is Pr(q|e) > p?

Note here that when e is the trivial instantiation, D-MAR reduces to asking whether Pr(q) > p, which is identical to D-PR.

We provide a number of results on these decision problems in this chapter. In particular, we show in Sections 11.2–11.4 that D-MPE is NP-complete, D-PR and D-MAR are PPcomplete, and D-MAP is NPPP-complete.