7
$\begingroup$

I assume the size of an instance of the SAT problem is measured by its number of (Boolean) variables. What is total number of instances of SAT problems of size N?

I guess that amounts to counting the number of "distinct" formulas that can be formed by N boolean variables, using a normal form such as CNF or DNF.

Update: this question is partly answered for the 3SAT case: https://cstheory.stackexchange.com/q/2168/15553

and the number of distinct clauses is: $$ C = 2N \times 2(N-1) \times 2(N -2) / 3! = 4 N(N-1)(N-2)/3 $$

$\endgroup$

migrated from cstheory.stackexchange.com Feb 26 '14 at 14:25

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ What kind of logical operators are allowed? Do you know how to count words in any language? $\endgroup$ – Raphael Mar 19 '14 at 8:25
  • 1
    $\begingroup$ What's the context where this problem arises? What's the motivation? Why do you care? How will you use the answer? And.... what have you tried? We expect you to make a serious effort to answer the question on your own before asking, and to show us in the question what you've tried. $\endgroup$ – D.W. Mar 19 '14 at 10:26
  • $\begingroup$ Sorry, I am temporarily too busy to think about this question, but I will update when I have time :) $\endgroup$ – Yan King Yin Jul 23 '15 at 3:09
6
$\begingroup$

If you consider 3-Conjunctive Normal Form (3CNF) (every clause has exactly three literals) and you allow clauses with repeated variables, then it is easy to see that using $N$ variables the number of different 3SAT clauses is $(2N)^3$ ($2N$ because every literal can appear unnegated or negated).

So the total number of distinct 3CNF formulas (without repeated clauses) is $2^{(2N)^3}$.

But be careful because the "size" of a 3CNF formula (e.g. considered as an input of a decision problem) is usually the size of its representation. For example, using alphabet $\Sigma = \{0,...,9,``,",-\}$ the 3CNF formula $(x_1\lor\bar{x}_2\lor x_3)\land (\lor x_2 \lor \bar{x}_3 \lor \bar{x}_4)$ can be represented with the string:

1,-2,3,2,-3,-4

and its length is 14.

$\endgroup$
5
$\begingroup$

A clause is comprised of literals over n variables. Let us assume that an instance is a subset of distinct clauses. We can obviously calculate the number of instances as the powerset of clauses, but that requires us to first clarify what we consider a valid clause.

In general, each variable will either be represented by one or both of its literals, or else it will be unrepresented. If the variable is represented, it may be represented through the positive literal only, the negative literal only, or both. Since there are 4 possible cases for each variable, and n variables, there must be $4^n$ possible clauses. Excluding the null clause we have $4^n -1$ total clauses and, excluding the null instance, $2^{4^n - 1}-1$ possible instances.

Of course, clauses that contain both literals of any variable aren't particularly useful; each one is satisfied by every assignment. Since these clauses don't really add any constraints, let's restrict our attention to constraining clauses.

In doing so, we eliminate the possibility of any variable taking both its literals, so we're left with three possible cases per variable, or $3^n$ possible clauses. Excluding the null clause and null collection again, we have $2^{3^n - 1}-1$ possible instances.

For k-SAT, each clause has exactly k literals. Obviously, there are $n\choose k$ ways to select k variables. Since we need exactly k literals per clause, however, we can only represent each variable with its positive or negative literal only. Thus, there must be $2^k{n \choose k}$ k-clauses, and $2^{2^k{n \choose k}}-1$ instances of k-sat.

Finally, note that we can also determine how many instances contain exactly c clauses.

  • For all possible clauses, excluding the null clause: ${4^n-1}\choose c$
  • For constraining clauses: ${3^n-1} \choose c$
  • For k-clauses: ${{2^k}{n\choose k}\choose c}$
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.