ON THE AVERAGE NUMBER OF SOLUTIONS FOR SAT INSTANCES

In this paper, we are interested in counting solutions for instances o f satisfiability and more precisely we try to extend the formula for t l-ie average number of solutions of random instances proposed in [4] t c a large class of instances. In fact the formula given in this refere nce works for the specific class cf instances where all clauses are de pendent. When we consider the independence characteristic of clauses, we find a more general mathematical expression. The computation of the average number of solutions with the actual formula depends only on t he structure of independence of the instance. The latter is defined to be the set of subsets of independent clauses. Searching the structure of independence for an instance is shown to be NP-hard. An algorithm in time O(nk(2)) is designed for finding an approximate structure of a n instance, k being the number of clauses and n the number of variable s of the instance. Even though an approximate structure of independenc e is considered in the calculation of the average number of solutions, our formula yields results with more accuracy.