  Finding the most probable explanation for observed variables in a Bayesian
network is a notoriously intractable problem, particularly if there are hidden
variables in the network. In this paper we examine the complexity of a related
problem, that is, the problem of finding a set of sufficiently dissimilar, yet
all plausible, explanations. Applications of this problem are, e.g., in search
query results (you won't want 10 results that all link to the same website) or
in decision support systems. We show that the problem of finding a 'good
enough' explanation that differs in structure from the best explanation is at
least as hard as finding the best explanation itself.
