---
title: "The Inferential Complexity of Bayesian and Credal Networks"
authors:
  - "Cassio Polpo de Campos"
  - "Fábio Gagliardi Cozman"
doi: ""
url: "https://ijcai.org/proceedings/2005/92"
pdf: "https://ijcai.org/proceedings/2005/0092.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "1313-1317"
track: ""
keywords:
---

# The Inferential Complexity of Bayesian and Credal Networks

Cassio Polpo de Campos, Fábio Gagliardi Cozman

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 1313-1317.

## Abstract

This paper presents new results on the complexity of graph-theoretical models that represent probabilities (Bayesian networks) and that represent interval and set valued probabilities (credal networks). We define a new class of networks with bounded width, and introduce a new decision problem for Bayesian networks, the maximin a posteriori. We present new links between the Bayesian and credal networks, and present new results both for Bayesian networks (most probable explanation with observations, maximin a posteriori) and for credal networks (bounds on probabilities a posteriori, most probable explanation with and without observations, maximum a posteriori).