New Limits for Knowledge Compilation and Applications to Exact Model Counting

Paul Beame, Vincent Liew

We show new limits on the efficiency of using current techniques to make exact probabilistic inference for large classes of natural problems. In particular we show new lower bounds…