TAOCP 7.1.4 Exercise 19
The reviewer correctly identifies that the previous argument failed because it treated $m_k$ as if it ranged over arbitrary subset sums without justifying how this arises from Algorithm B.
Section 7.1.4: Binary Decision Diagrams
Exercise 19. [20] [20] What are the largest and smallest possible values of variable mk in Algo- rithm B, based only on the weights (w1, . . . , wn), not on any details of the function f?
Verified: no
Solve time: 5m
The reviewer correctly identifies that the previous argument failed because it treated $m_k$ as if it ranged over arbitrary subset sums without justifying how this arises from Algorithm B. The correction is to go back to what $m_k$ actually is in the algorithm and then characterize its possible values by valid constructions inside the model of ordered decision diagrams used in TAOCP 7.1.4.
1. Meaning of $m_k$ in Algorithm B
In Algorithm B, variables $x_1,\dots,x_n$ are processed in fixed order. At stage $k$, the computation is at a node representing a cofactor of the Boolean function $f$, where variables $x_1,\dots,x_{k-1}$ have already been fixed by the current path.
The quantity $m_k$ is defined purely from the remaining variables $x_k,\dots,x_n$ and their weights $w_k,\dots,w_n$. It represents the contribution that can still arise from variables not yet resolved by the current cofactor of $f$. Concretely, $m_k$ depends only on which of the remaining variables are still capable of affecting the value of the function at that node in the decision diagram induced by $f$.
Thus, $m_k$ is not an arbitrary quantity attached to $f$, but is determined by a subset of indices
$$ S_k \subseteq {k,k+1,\dots,n} $$
consisting of those variables that are still “live” (i.e., not eliminated by the cofactor becoming independent of them at that node). In Algorithm B, this leads to
$$ m_k = \sum_{i \in S_k} w_i. $$
So the question becomes: what subsets $S_k$ can actually arise at level $k$, when we range over all Boolean fu_