4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Related post: Lower bounds on #SAT? $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 30 '11 at 1:22
  • $\begingroup$ @Ariston: So the only difference between your question and user1749's question is that user1749 asks for $k=3$, while you're asking for a general $k$. $\endgroup$ – Giorgio Camerani Mar 30 '11 at 8:14
  • $\begingroup$ (Sorry, I made a mistake in the location of my comment, so I post it again at the right place). Not exactly, my question deals with the complexity of the problem not with how to compute an answer. – Ariston $\endgroup$ – user4432 Mar 30 '11 at 10:06
  • $\begingroup$ @Ariston: OK, so a further difference between your question and user1749's question is that he asks how many instances are satisfiable, while you ask which is the complexity of determining how many instances are satisfiable. $\endgroup$ – Giorgio Camerani Mar 30 '11 at 12:31
  • $\begingroup$ Exactly, tks Walter for clarifying my question. $\endgroup$ – user4432 Mar 30 '11 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy