---
title: "The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages"
authors:
  - "Denis Deratani Mauá"
  - "Cassio Polpo de Campos"
  - "Fábio Gagliardi Cozman"
doi: ""
url: "https://ijcai.org/proceedings/2015/130"
pdf: "https://ijcai.org/proceedings/2015/0130.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "889-894"
track: "Main Track"
keywords:
---

# The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages

Denis Deratani Mauá, Cassio Polpo de Campos, Fábio Gagliardi Cozman

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 889-894.

## Abstract

We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as context-sensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.