The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages
Denis Deratani Mauá, São Paulo, Cassio P. De Campos, Fábio Gagliardi Cozman · Research Portal (Queen's University Belfast) · 2015
We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logi-cal 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 intro-duced by evidence alone. 1