TAOCP 7.2.2.2 Exercise 189

Section 7.2.2.2: Satisfiability

Exercise 189. [27] [27] Apply BDD methods to random $k$SAT problems on 50 variables. What is the approximate BDD size after $m$ distinct clauses have been ANDed together, as $m$ grows?

Verified: no
Solve time: 2m16s

Solution

Let $n=50$. The question concerns the behavior observed when applying BDD methods to random $k$SAT formulas while clauses are added one by one. The relevant quantity is not the worst-case number of nodes in a BDD, but the typical number of distinct residual functions created after $m$ random clauses have been conjoined.

The BDD size depends strongly on the variable ordering. To make the question well-defined, assume a standard experimental setting: a fixed ordering of the $50$ variables is chosen, such as a random ordering or the natural ordering $x_1,\ldots,x_{50}$, and the BDD is maintained after each new clause is ANDed into the existing formula.

For a variable ordering, a node at level $i$ represents a residual Boolean function obtained after assigning values to the first $i$ variables. Two partial assignments merge into one BDD node exactly when they leave the same residual formula on the remaining $50-i$ variables. Hence the BDD size after $m$ clauses is determined by the number of distinct residual subproblems produced by the first $m$ clauses.

For very small $m$, only a small number of clauses constrain the variables. Many partial assignments produce identical residual formulas, so the BDD remains compact. If $m=0$, the function is the constant $1$, and the BDD consists only of the terminal $1$ node.

As $m$ increases, the clauses introduce more independent restrictions. The number of possible residual functions increases because different partial assignments are distinguished by the clauses that they satisfy, violate, or leave unresolved. Therefore the number of BDD nodes increases rapidly once enough clauses have accumulated to separate many prefixes of the variable ordering.

The important point is that this growth is an empirical BDD-complexity transition, not the SAT satisfiability threshold. The satisfiability threshold describes when the probability that the formula has a satisfying assignment changes sharply as a function of clause density $m/n$. BDD blow-up is controlled instead by the number of distinct residual functions under the chosen ordering. These two transitions are related through the structure of the formula but are not identical, and one cannot infer the BDD transition point from the SAT threshold alone.

For random $k$SAT instances on $50$ variables, experiments with BDD construction show the following typical behavior as $m$ grows:

$$ \begin{array}{c|c} \text{Number of clauses }m & \text{Typical BDD behavior}\ \hline \text{small }m & \text{Small BDD with strong merging of residual functions}\ \text{intermediate }m & \text{Rapid growth as residual functions become distinct}\ \text{large }m\text{ while the formula remains satisfiable} & \text{Large BDD approaching exponential size}\ \text{very large }m & \text{Possible collapse to the false terminal when contradictions dominate} \end{array} $$

Thus the observed curve is not a monotone sigmoid. The size generally increases during the phase where clauses are creating many distinct residual functions, but it can fluctuate because adding clauses can also simplify the function. In particular, once the conjunction becomes unsatisfiable, the BDD collapses to the constant false function, which has only one terminal node.

A useful approximation for the measured curve is therefore a rise-and-collapse curve:

$$ S(m)\approx \begin{cases} O(1)\text{ to polynomial in }m, & m\text{ small},\[4pt] \text{rapid exponential growth in the number of active residual states}, & m\text{ in the BDD-hard region},\[4pt] 1, & m\text{ after the formula becomes forced unsatisfiable}. \end{cases} $$

During the hard region, the BDD size is governed by the number of distinct residual functions. If most prefixes of the variable ordering lead to different residual formulas, then the BDD contains nearly the maximum number of useful states. At level $i$, there can be at most $2^i$ distinct assignments to the first $i$ variables, so the absolute worst-case size of a reduced ordered BDD is bounded by the complete decision tree:

$$ 1+2+4+\cdots+2^{50}=2^{51}-1. $$

This bound is not the expected size of a random $k$SAT BDD. It only gives the maximum possible number of nodes. The experimental observation is that random formulas enter a region where the BDD becomes exponentially large in $n$, but the exact node count depends on $k$, clause density, variable ordering, and the BDD package's reduction heuristics.

For $n=50$, the approximate behavior can therefore be summarized as follows:

$$ \boxed{ S(m)\text{ starts small, grows rapidly as clauses create distinct residual functions, reaches an exponential peak region, and may collapse when the formula becomes unsatisfiable.} } $$

The key quantitative feature is that the peak BDD size in the hard region is exponential in the number of variables:

$$ S_{\max}(m)=2^{\Theta(50)}, $$

with the exact value determined experimentally rather than by the worst-case bound $2^{51}-1$. The exercise is therefore about the measured BDD growth curve as clauses accumulate, not about the final worst-case size of an arbitrary $50$-variable Boolean function.