Conditional Lower Bounds on the Complexity of Probabilistic Inference
Johan Kwisthout, Hans L. Bodlaender · 2009
The Inference problem in probabilistic networks (given a stochastic variable V , what is the posterior probability that V = v given evidence e?) has been proven to be intractable; in fact, has a PP-complete decision variant [17]. The currently most efficient algorithms for this problem are all exponential in the treewidth of the moralised graph of the network. We prove, using a recent result of Marx [18], that these algorithms are in some sense optimal: we prove a lower bound of f(G) tw(G) log tw(G) ) for any algorithm solving arbitrary instances of Inference with graph G, unless the ETH fails. To obtain this lower bound we introduce treewidth-preserving reductions which may be of independent interest.