Computational complexity of local posteriori inference algorithms in algebraic Bayesian networks.
Alexander Vladimirovich Sirotkin · Informatics and Automation · 2014
The paper presents algorithmical complexity estimates for local posteriori inference in algebraic Bayesian networks. We consider the ways of implementing the inference for three types of evidence (deterministic, stochastic, and imprecise). If we need to solve linear programming tasks for inference, the comlexity estimations are given in numbers of such tasks and numbers of variables and constraints in each task. In other cases, complexity estimates are given in numbers of arithmetic operations.