Number of solutions to satisfiability instances—Applications to knowledge bases

"In propositional logic (zero order) a system of logical rules may be put under the form of a conjunction of disjunction, i.e. a “satisfiability” or SAT-problem. SAT is central to NP-complete problems. Any result obtained on SAT would have consequences for a lot of problems important in artificial intelligence. We deal with the question of the number N of solutions of SAT. Firstly, any system of SAT clauses may be transformed in a system of independent clauses by an exponential process; N may be computed exactly. Secondly, by a statistical approach, results are obtained showing that for a given SAT-instance, it should be possible to find an estimate of N with a margin of confidence in polynomial time. Thirdly, we demonstrate the usefulness of these ideas on large knowledge bases." Int. J. Patt. Recogn. Artif. Intell. 03, 53 (1989).