TAOCP 7.2.2.2 Exercise 148
Equation (66) defines a bound $C_{\max}(d)$ on the number of candidate nodes considered by the search procedure at depth $d$ of the backtracking process.
Section 7.2.2.2: Satisfiability
Exercise 148. [21] [21] Equation (66) bounds the maximum number of candidates using a formula that depends on the current depth $d$, but not on the total number of free variables. The same cutoffs are used in problems with any number of variables. Why is that a reasonable strategy?
Verified: yes
Solve time: 59s
Solution
Equation (66) defines a bound $C_{\max}(d)$ on the number of candidate nodes considered by the search procedure at depth $d$ of the backtracking process. The key structural feature of the search is that a node at depth $d$ corresponds to a partial assignment fixing exactly $d$ variables, while the remaining variables are still free.
For any instance with at least $d$ variables, the search tree up to depth $d$ is determined entirely by the choices of the first $d$ branching steps. Each branching step splits a node into at most two children, corresponding to assigning a chosen variable either true or false. Consequently, the total number of nodes at depth $d$ is bounded by $2^d$, and any more refined bound used in (66) depends only on how clause propagation and pruning reduce this worst-case growth along the first $d$ decisions.
If an instance has fewer than $d$ variables, the search terminates before reaching depth $d$, so the bound $C_{\max}(d)$ is trivially valid because the actual number of candidates is then smaller than any bound computed for deeper levels. Thus the same function $C_{\max}(d)$ applies uniformly to all instances, independently of their total number of variables.
The dependence on $d$ alone is therefore sufficient because the relevant combinatorial explosion is governed by the depth of branching, not by the global size of the variable set. The total number of variables only determines the maximum possible depth of the tree; it does not affect the local branching structure at levels $0$ through $d$. Any sharper dependence on the total number of variables would not improve correctness of the bound, since the worst case for fixed $d$ is realized already in instances with at least $d$ variables.
Clause propagation and the BIMP-style reductions used in Algorithm L act locally on the current partial assignment. Their effect at depth $d$ depends on which $d$ variables have been fixed, not on how many variables remain globally. Therefore the cutoff in (66) is naturally expressed as a function of depth alone, since all relevant pruning behavior is determined by information available within the current search prefix.
This justifies using a uniform depth-based cutoff $C_{\max}(d)$ across all SAT instances regardless of their total number of variables. ∎