On the Complexity of Strong and Epistemic Credal Networks

Denis Deratani Mauá, Cassio Polpo de Campos, Alessio Benavoli, Alessandro Antonucci

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review


Credal networks are graph-based statistical models whose parameters take values on a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The result of inferences with such models depends on the irrelevance/independence concept adopted. In this paper, we study the computational complexity of inferences under the concepts of epistemic irrelevance and strong independence. We strengthen complexity results by showing that inferences with strong independence are NP-hard even in credal trees with ternary variables, which indicates that tractable algorithms, including the existing one for epistemic trees, cannot be used for strong independence. We prove that the polynomial time of inferences in credal trees under epistemic irrelevance is not likely to extend to more general models, because the problem becomes NP-hard even in simple polytrees. These results draw a definite line between networks with efficient inferences and those where inferences are hard, and close several open questions regarding the computational complexity of such models.
Original languageEnglish
Title of host publication29th Conference on Uncertainty in Artificial Intelligence (UAI)
PublisherMorgan Kaufmann
Number of pages10
Publication statusPublished - 2013


Dive into the research topics of 'On the Complexity of Strong and Epistemic Credal Networks'. Together they form a unique fingerprint.

Cite this