On the complexity of inference about probabilistic relational models

The result that assuming NETIME ≠ ETIME this problem is not polynomial for reasonably expressive representation systems is obtained, which means it is unlikely to find inference techniques with a better worst-case behavior than the commonly employed strategy of constructing standard Bayesian networks over ground atoms.

Abstract

We investigate the complexity of probabilistic inference from knowledge bases that encode probability distributions on finite domain relational structures. Our interest here lies in the complexity in terms of the domain under consideration in a specific application instance. We obtain the result that assuming NETIME≠ETIME this problem is not polynomial for reasonably expressive representation systems. The main consequence of this result is that it is unlikely to find inference techniques with a better worst-case behavior than the commonly employed strategy of constructing standard Bayesian networks over ground atoms (knowledge based model construction).