8
$\begingroup$

Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is unsatisfiable, then $s_f$ will be the empty set.) Let's consider all the possible sets of truth assignments that we can specify by these formulas: $$S(N,M)=\{s_f | f\in F(N,M)\}$$ Finally, define the size of this set of sets as $$T(N,M) = |S(N,M)|$$

If we keep our variables fixed and keep adding clauses, we can express more complicated sets $s_f$. I had always assumed that for some sufficiently large $M$, I could express any set of assignments. In other words, if we define $$W(N)=\max_M T(N,M)$$ then I had assumed that $$W(N)=2^{2^N}$$

However, this is not true; there are forbidden sets of assignments that cannot be expressed by 3-SAT. This is easy to see-- each clause of a 3-SAT formula forbids 1/8th of the possible truth assignments, so we cannot have a set of assignments with at least one but less than 1/8th of the assignments forbidden. For example, there is no $f\in F(4,M)$ such that $|s_f|=15$, regardless of how big we make $M$. It follows that for $N>3$, $$W(N) < 2^{2^N}$$

But that might just be the tip of the iceberg in terms of "missing" sets. Define the size of the missing sets as: $$V(N) = 2^{2^N} - W(N)$$ Question: How does $V(N)$ grow with $N$? Or, equivalently, how does $W(N)$ grow with $N$?

(There's a second question about growth in $N$ and $M$ that I will ask separately.)

Edit #1: Although it's probably not helpful for the asymptotics, I enumerated $T(N,M)$ to convergence for small $N$. For $N<6$, the calculation is complete (i.e., the set does not grow by adding more clauses). Modulo programming bugs, I get:

$T(N,M)$ $M=0$ $M=1$ $M=2$ $M=3$ $M=4$ $M=5$ $M=6$ $M=7$ $M=8$ $M=9$ $M=10$ $M=11$ $M=12$
$N=1$ 1 3 4
$N=2$ 1 9 16
$N=3$ 1 27 158 246 256
$N=4$ 1 65 1,430 11,334 31,402 41,746 43,074 43,138 43,146
$N=5$ 1 131 6,992 193,872 2,766,512 19,160,896 62,432,832 103,652,512 117,960,004 120,336,724 120,509,092 120,510,052 120,510,132
$N=6$ 1 233 24,084 1,459,044 56,328,304 1,382,172,232 ?
$N=7$ 1 379 66,586 7,224,786 538,779,796 ?

Note that $T(N,0)=1$ and $$T(N,1)=8{M \choose 3} + 4{M \choose 2} + 2{M\choose 1} + 1$$

For $N\leq 5$ we have convergence; the summarized results are:

$W(N)$ $2^{2^N}$
$W(1)$=4 4
$W(2)$=16 16
$W(3)$=256 256
$W(4)$=43,146 65,536
$W(5)$=120,510,132 4,294,967,296

Edit #2: We can translate the "each clause forbids 1/8th of the truth assignments" observation above into an explicit bound using large deviation theory. Let $P$ be a Bernoulli distribution with probability 7/8 of zero and $H(P)$ be its entropy. Then, ignoring sub-exponential terms: $$V(N) \geq 2^{H(P)\times N} = 2^{0.543564443... \times N}$$

$\endgroup$
2
  • $\begingroup$ Trivially $W(N) \leq 2^{\sum_{k = 0}^3 {2N \choose k}}$, which is much smaller than $2^{2^N}$ for large $N$. $\endgroup$ Nov 27, 2021 at 21:51
  • $\begingroup$ @MikhailTikhomirov That is an excellent point! I guess that's about $2^{(4/3)N^3}$ asymptotically. $\endgroup$ Nov 27, 2021 at 23:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.