Tractable probabilistic models and computational complexity

Abstract Probabilistic models with tractable marginalization are those in which evidence queries involving marginalization of variables are guaranteed to be computable in polynomial time in the size of the model. The tractability of marginalization of current classes of tractable probabilistic models is achieved through structural properties imposed over the functions they decompose to and it is an open question whether there are more general classes of probabilistic models with tractable marginalization than the current ones. That question is settled in this paper by the usage of boolean circuits to express them. On one hand, bounds on the number of simple and local operations required by a circuit to solve a problem are used as measures of complexity and on the other the circuit value problem is guaranteed to have complexity bounded by a polynomial function on the number of its gates. It is shown that choices of the definitions of the variables to use have an impact on the circuit description length as they are paramount to definitions of simplicity and locality. The framework that is put forward builds on a construction of a circuit representation of a dataset and on the definition of problems that take that circuit as an input such that the answers of the problems correspond to values of interest. Based on that, a set of circuit value problems are defined so that given inputs that identify queries of interest, the corresponding output values are obtained as a result of evaluation of those circuits. This approach is more general than current ones, in that, for any algorithm that runs in polynomial time over a model there is a circuit with number of gates bounded by a polynomial function of the time that the algorithm takes to be executed.