Many AI problems, when formalized, reduced to evaluating the probability that a propositional expression is true. In this paper we show that this problem is computationally intractable even in surprisingly restricted cases and even if we settle for an approimation to this probability.

We consider various methods used in approximate reasoning such as computing degree of belief and Bayesian belief networks, as well as reasoning techniques such as constraint satisfaction and knowledge compilation, that use approximation to avoid computational difficulties, and reduce them to model-counting problems over a propositional domain.

We prove that counting satisfying assignments of propositional logic is intractable even for Hron and monotone fomulae, and even when the size of clauses and number of occurences of the variables are extremely limited. This should be contrasted with the case of deductive reasoning, where Horm theories and theories with binary clauses are distinguished by the existence of linear time satisfiability algorithms. What is even more surprising is that, as we show, even approximating the number of satisfying assiggnments (i.e., "approximating" approimate reasoning), is intractable for most of these restricted theories.

We also identify some restricted classes of propositional formulae for which efficient algorithms for counting assignments can be given.