Finding MAPs for belief networks is NP-hard (Q1332845)

The paper studies the computational complexity of abductive reasoning in Bayesian belief networks, which are directed acyclic graphs augmented with conditional probability distributions residing in each node. Such networks can be modeled by finding posterior distribution given some evidence, by finding a maximum a-posterori probability (MAP) instantiation of all of the variables (representing nodes) in the network, or by other schemes. This paper is primarily concerned with complexity issues of finding a maximum a-posteori probability, called the MAP problem. The latter is defined as follows: Given a probability distribution over a set of variables \(V\), the evidence \(E\) which is an instantiation of a set of variables \(E \subseteq V\), find value assignment \(A\) to all of the variables \(V\) that maximizes \(P(A | E)\). It is shown that finding a maximum a-posterori probability is NP-hard in the general case, even if the size of the network is linear. To prove this result, a related problem called MAPBNETD is considered. The latter is defined as follows: Given a belief network, find whether there is an instantiation of variables such that its probability is at least \(P\). The result about the complexity of the MAP problem is extended to belief networks with several topological restrictions. The MAP problem is also discussed for other graph representations, and it is shown that the proof presented in this paper can be used to improve the results stated by [\textit{G. F. Cooper} [Artif. Intell. 42, No. 2/3, 393-405 (1990; Zbl 0717.68080)].