To continue the question posted by user1749 on Oct 13 2010 : How many instances of 3-SAT are satisfiable? Which was:
Consider the 3-SAT problem on n variables. The number of possible distinct clauses is:
$$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$
The number of problem instances is the number of all subsets of the set of possible clauses: $I = 2^C$. Trivially, for each $n \ge 3$, there exist at least one satisfiable instance and one unsatisfiable instance. Is it possible to calculate, or at least estimate, the number of satisfiable instance for any given n?
I was wondering what the complexity of the problem of counting the satisfiable instances of k-SAT on n variables is.