What is the complexity of #satisfiable instances of k-SAT ?

Asked Mar 30 '11 at 00:08

Active Mar 30 '11 at 05:29

Viewed 296 times

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.

edited Apr 13 '17 at 12:32

Community

asked Mar 30 '11 at 00:08

2

Related post: Lower bounds on #SAT? – Hsien-Chih Chang 張顯之 Mar 30 '11 at 01:22
@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$. – Giorgio Camerani Mar 30 '11 at 08:14
(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 – Mar 30 '11 at 10:06
@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. – Giorgio Camerani Mar 30 '11 at 12:31
Exactly, tks Walter for clarifying my question. – Mar 30 '11 at 12:59

What is the complexity of #satisfiable instances of k-SAT ?

0 Answers0