Section 7.2.2.2: Satisfiability

Exercise 188. [HM25] [HM25] Analyze random 1SAT, the case $k = 1$: What are $S_{1,n}$ and $\hat{S}_{1,n}$?

Verified: no
Solve time: 6m11s

---

Solution

In the random SAT model used here, a formula with $m$ clauses is formed by choosing each clause independently and uniformly from the possible clauses. For $k=1$, there are $2n$ possible clauses,

$$ x_1,\bar x_1,x_2,\bar x_2,\ldots,x_n,\bar x_n . $$

Thus a random formula is an ordered $m$-tuple of literals, and the total number of possible formulas is

$$ (2n)^m . $$

A 1SAT formula is satisfiable exactly when no variable occurs with both signs. Repeated occurrences of the same literal cause no difficulty.

To compute $S_{1,n}(m)$, count the formulas having this property. Suppose exactly $r$ variables occur in the formula. We first choose these variables,

$$ \binom nr . $$

For each such variable, only one of its two signs may occur, so the signs can be chosen in

$$ 2^r $$

ways. After the signs are fixed, the $m$ clause positions must be filled with these $r$ chosen literals, and every one of the $r$ literals must occur at least once. The number of such ordered sequences is the number of onto maps from an $m$-element set to an $r$-element set,

$$ r!\left{\begin{matrix}m\r\end{matrix}\right}, $$

where the braces denote a Stirling number of the second kind. Therefore the number of satisfiable formulas is

$$ \sum_{r=0}^{\min(n,m)} \binom nr 2^r r! \left{\begin{matrix}m\r\end{matrix}\right}. $$

Dividing by the total number $(2n)^m$ of possible random formulas gives

$$ \boxed{ S_{1,n}(m)

\frac{1}{(2n)^m} \sum_{r=0}^{\min(n,m)} \binom nr 2^r r! \left{\begin{matrix}m\r\end{matrix}\right}. } $$

This formula also covers $m=0$, since the empty formula is satisfiable.

For $\widehat S_{1,n}(m)$, fix an assignment of the $n$ variables. Exactly one of the two possible literals for each variable is true, so exactly $n$ of the $2n$ possible unit clauses are satisfied by this assignment. A random clause is therefore satisfied with probability

$$ \frac{n}{2n}=\frac12 . $$

Because the $m$ clauses are chosen independently, the probability that this fixed assignment satisfies the whole formula is

$$ \left(\frac12\right)^m . $$

There are $2^n$ possible assignments, and by linearity of expectation the expected number of satisfying assignments is the sum of these probabilities over all assignments. Hence

$$ \widehat S_{1,n}(m)

2^n\left(\frac12\right)^m, $$

so

$$ \boxed{ \widehat S_{1,n}(m)=2^{,n-m}. } $$

Thus random 1SAT has the exact forms

$$ \boxed{ S_{1,n}(m)

\frac{1}{(2n)^m} \sum_{r=0}^{\min(n,m)} \binom nr 2^r r! \left{\begin{matrix}m\r\end{matrix}\right} } $$

and

$$ \boxed{ \widehat S_{1,n}(m)=2^{,n-m}. } $$

The first quantity is the probability that no variable receives conflicting unit clauses, while the second follows directly from the probability that a fixed assignment satisfies all independently sampled clauses.