  Credal networks are graph-based statistical models whose parameters take
values in a set, instead of being sharply specified as in traditional
statistical models (e.g., Bayesian networks). The computational complexity of
inferences on such models depends on the irrelevance/independence concept
adopted. In this paper, we study inferential complexity under the concepts of
epistemic irrelevance and strong independence. We show that inferences under
strong independence are NP-hard even in trees with ternary variables. We prove
that under epistemic irrelevance the polynomial time complexity of inferences
in credal trees is not likely to extend to more general models (e.g. singly
connected networks). These results clearly distinguish networks that admit
efficient inferences and those where inferences are most likely hard, and
settle several open questions regarding computational complexity.
