Section 7.2.2.2: Satisfiability

Exercise 215. ▶ [HM23] What is the expected profile of the search tree when a simple backtrack procedure is used to find all solutions to a random 3SAT problem with $m$ independent clauses on $n$ variables? (There is a node on level $l$ for every partial solution $x_1 \ldots x_l$ that doesn't contradict any of the clauses.) Compute these values when $m = 200$ and $n = 50$. Also estimate the total tree size when $m = \alpha n$, for fixed $\alpha$ as $n \to \infty$.

Verified: yes
Solve time: 3m13s

---

Solution

Let $A_l$ be the number of nodes on level $l$ of the backtrack tree. A node on level $l$ corresponds to a partial assignment of the variables $x_1,\ldots,x_l$ that does not contradict any clause.

Fix a particular assignment of the first $l$ variables. A random 3SAT clause is contradicted by this assignment exactly when all three variables of the clause occur among $x_1,\ldots,x_l$, and every literal has the sign opposite to the assigned value.

The probability that the three variables are chosen from the first $l$ variables is

$$ \frac{\binom l3}{\binom n3}. $$

Given this event, each of the three literals has probability $1/2$ of being false, independently, so the probability that the whole clause is falsified is

$$ \frac18. $$

Hence a single clause contradicts the partial assignment with probability

$$ r_l=\frac{\binom l3}{8\binom n3}. $$

The clauses are independent, so the probability that a fixed partial assignment survives all $m$ clauses is

$$ (1-r_l)^m

\left(1-\frac{\binom l3}{8\binom n3}\right)^m . $$

There are $2^l$ assignments to the first $l$ variables. Therefore, by linearity of expectation,

$$ \boxed{ \mathop{\rm E}(A_l)

2^l \left(1-\frac{\binom l3}{8\binom n3}\right)^m } $$

with the convention that $\binom l3=0$ for $l<3$.

This gives the expected profile of the search tree.

For $m=200$ and $n=50$,

$$ \mathop{\rm E}(A_l)

2^l \left(1-\frac{\binom l3}{8\binom{50}3}\right)^{200}. $$

Evaluating this expression for all $0\le l\le50$ gives the following representative values:

$$ \begin{array}{c|r} l&\mathop{\rm E}(A_l)\ \hline 0&1.0000\ 1&2.0000\ 2&4.0000\ 5&31.5944\ 10&878.6195\ 15&18324.7319\ 20&243665.1764\ 25&1746766.9818\ 30&5652563.5483\ 31&6390728.8106\ 32&6934053.8202\ 33&7208083.5492\ 34&7166247.4261\ 35&6801813.8873\ 40&2444398.9671\ 45&202830.8971\ 50&2838.6405 \end{array} $$

The largest expected level occurs at

$$ l=33, $$

where

$$ \boxed{ \max_l\mathop{\rm E}(A_l)

7208083.5492\ldots } $$

The expected total number of nodes in the tree is

$$ \mathop{\rm E}(|T|)

\sum_{l=0}^{50} 2^l \left(1-\frac{\binom l3}{8\binom{50}3}\right)^{200}. $$

Numerically,

$$ \boxed{ \mathop{\rm E}(|T|)

85569279.0627\ldots } $$

so the expected tree contains roughly $8.6\times10^7$ nodes.

Now consider the asymptotic case

$$ m=\alpha n $$

for fixed $\alpha$, with $n\to\infty$. Write

$$ l=xn,\qquad 0\le x\le1 . $$

For fixed $x$,

$$ \frac{\binom{xn}{3}}{\binom n3}\sim x^3 . $$

Therefore the expected number of nodes at level $xn$ satisfies

$$ \mathop{\rm E}(A_{xn}) \sim 2^{xn} \left(1-\frac{x^3}{8}\right)^{\alpha n}. $$

Taking logarithms gives

$$ \frac1n\log \mathop{\rm E}(A_{xn}) \sim \Phi_\alpha(x), $$

where

$$ \Phi_\alpha(x)

x\log 2+ \alpha\log\left(1-\frac{x^3}{8}\right). $$

The total expected tree size is a sum of exponentially many terms, so its exponential growth rate is determined by the largest exponent:

$$ \boxed{ \mathop{\rm E}(|T|)

\exp\left( n\max_{0\le x\le1}\Phi_\alpha(x)+o(n) \right). } $$

The maximizer need not always be an interior point. The function must be maximized on the entire closed interval $0\le x\le1$.

For an interior maximizer,

$$ \Phi_\alpha'(x)=0. $$

Differentiating,

$$ \Phi_\alpha'(x)

\log2

\alpha \frac{3x^2/8}{1-x^3/8}. $$

Thus an interior critical point satisfies

$$ \log2

\alpha\frac{3x^2}{8-x^3}, $$

or equivalently,

$$ \boxed{ \alpha

\frac{(8-x^3)\log2}{3x^2}. } $$

However, this equation only applies when the maximum lies in $0<x<1$. If the largest value of $\Phi_\alpha(x)$ occurs at $x=1$, then the boundary point gives the dominant contribution instead. Therefore the complete asymptotic estimate is

$$ \boxed{ \mathop{\rm E}(|T|)

\exp\left( n\max_{0\le x\le1} \left[ x\log2+ \alpha\log\left(1-\frac{x^3}{8}\right) \right] +o(n) \right). } $$

The comparison with the complete binary tree of size $2^{n+1}-1$ depends on $\alpha$. The full tree has exponential rate $\log2$, whereas the backtrack tree has exponential rate

$$ \max_{0\le x\le1}\Phi_\alpha(x). $$

For values of $\alpha$ where this maximum is strictly less than $\log2$, the expected search tree is exponentially smaller than the complete binary tree. For sufficiently small $\alpha$, the maximum approaches $\log2$, so this strict reduction in exponential order does not hold uniformly for all $\alpha$. $\square$