HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Number of instances of SAT (boolean satisfiability) problems of size N?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
satnumberbooleaninstancessizesatisfiabilityproblems

Problem

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 $$

Solution

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.

Code Snippets

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

Context

StackExchange Computer Science Q#22054, answer score: 6

Revisions (0)

No revisions yet.