Reference: Cooper, G. F. Probabilistic Inference Using Belief Networks Is NP-Hard. Knowledge Systems Laboratory, 1987.
Abstract: Most natural and manmade systems contain partial dependencies among their compsistional elements. In medicine, for example, the existence of a finding is generally dependent on some of the other findings and other diseases, but never dependent on all the other findings and diseases. It is this partial dependency structure that makes our world both interesting and at the same time comprehesible. Even so, our models of real-world problem domains are almost always incomplete because all the relevant variables and relationships are not known. It is for this reason that models that most accurately reflect available knowledge are often probabilistic. Thus real-world domains quite naturally lead to partial dependency graph models that are probabilistic. The graphical representation of probabilistic relationships among events has been the subject of considerable research. Markov models form one such class of probabilistic graphical representations [Kemeny 76, Darroch 80]. In the field of artificial intelligence, numerous systems have used a directed graph to represent probabilistic relationships among events [Duda 76, Weiss 78]. A particular type of probabilistic graphical representation, called belief networks, has been defined and explored by numerous researchers. In addition to being called belief networks [Pearl 86], they have been termed causal nets [Good 61a, Good 61b], probabilistic cause-effect models [Rousseau 68], probabilistic causal networks [Cooper 84], and influence diagrams [Howard 84, Shachter 86]. A primary advantage of using a graphical representation of probabilistic relationships is the efficiency that results. It is necessary to consider only the known dependencies among variables (events) in a domain, rather that to assume that all variables are dependent on all other variables [Cooper 84, Pearl 87a]. This generally leads to greatly improved efficiency in the acquisition and representation of domain knowledge and in the computations that are used to solve problems in the domain.