Exercise 159. [20] [20] John Conway’s basic rule for Life, exercise 7.1.3–167, is a Boolean function L(xNW, xN, xNE, xW, x, xE, xSW, xS, xSE). What ordering of those nine variables will make the BDD as small as possible?

Verified: no
Solve time: 6m03s

Solution

Let $p=n-m$ and write $k_1=\lfloor p/3\rfloor$, $k_2=\lceil 2p/3\rceil$. The function is

$$ f(x_1,\dots,x_n)

[x_1+\cdots+x_p=k_1] + [x_1+\cdots+x_p=k_2]; g(x_{p+1},\dots,x_n). $$

A BDD node under a fixed ordering is determined by a prefix of variables and the values of all subfunctions reachable after that prefix. For the first $p$ variables, every node reached after reading $(x_{\pi(1)},\dots,x_{\pi(i)})$ is determined by the pair $(i,s)$, where $s$ is the number of 1s among the first $i$ examined variables together with the remaining number of unseen variables among $x_1,\dots,x_p$. Two such states are distinct whenever they induce different sets of continuations to the accepting conditions $s=k_1$ or $s=k_2$.

Consecutive block ordering of $x_1,\dots,x_p$

Assume $\pi$ places $x_1,\dots,x_p$ consecutively. After $i$ variables, the state is determined by $(i,s)$ with $0\le s\le i$. From such a state, the remaining $p-i$ variables can contribute at most $p-i$ additional 1s, so only values $s$ satisfying

$$ k_1-(p-i)\le s\le k_2 $$

can still lead to satisfaction of at least one of the two predicates.

Thus, at level $i$, admissible states are those integers $s$ in the intersection

$$ 0\le s\le i,\qquad k_1-(p-i)\le s\le k_2. $$

Hence the number of nodes at level $i$ equals

$$ N_i=\max\Bigl(0,;\min(i,k_2)-\max(0,k_1-(p-i))+1\Bigr). $$

Write $k_1=\frac{p}{3}+O(1)$ and $k_2=\frac{2p}{3}+O(1)$. For indices $i$ in the central range $\frac{p}{3}\le i\le \frac{2p}{3}$, both constraints are active and the interval simplifies to

$$ k_1-(p-i)\le s\le i, $$

whose length is

$$ i-\bigl(k_1-(p-i)\bigr)+1

2i-p+k_1+1

2i-\frac{2p}{3}+O(1). $$

This grows linearly from $O(1)$ at $i\approx p/3$ to $\frac{2p}{3}+O(1)$ at $i\approx 2p/3$ and then stabilizes at $k_2-k_1+1=\frac{p}{3}+O(1)$ for $i\ge 2p/3$.

Summing over all levels,

$$ \sum_{i=0}^{p} N_i

\sum_{i=0}^{p} \left(\frac{1}{3}p + O!\left(\min(i,p-i)\right)\right). $$

The linear ramp in the middle contributes a quadratic area equal to the area of a trapezoid of height $\frac{p}{3}$ over width $p$, hence

$$ \sum_{i=0}^{p} N_i = \frac{1}{3}p^2 + O(p). $$

Each such state corresponds to a distinct BDD node, and all sinks and the $g$-attachments contribute only $O(n)$ additional nodes because only the two accepting states at level $p$ connect to a fixed BDD for $g$. Therefore,

$$ B(f^\pi)=\frac{1}{3}p^2+O(p)=\frac{1}{3}n^2+O(n). $$

Split ordering of the $x$-variables

Assume $\pi$ places approximately $p/2$ of ${x_1,\dots,x_p}$ at the beginning and the rest at the end, with the $m$ variables for $g$ between them.

Let $p_1\approx p/2$ be the number of early $x$-variables and $p_2\approx p/2$ the number of late ones. After the first block, the BDD must represent all partial sums $s\in[0,p_1]$, giving $\Theta(p_1^2)$ nodes in the standard counting construction:

$$ \sum_{i=0}^{p_1} (i+1)=\frac{1}{2}p_1^2+O(p_1). $$

After the middle block, the second half of the $x$-variables behaves independently, producing another triangular DP of size

$$ \frac{1}{2}p_2^2+O(p_2). $$

The two halves are separated by the variables of $g$, so no sharing of intermediate sum states is possible between them; the BDD therefore contains both structures disjointly up to $O(n)$ sink and interface nodes. Hence

$$ B(f^\pi)=\frac{1}{2}p_1^2+\frac{1}{2}p_2^2+O(n) =\frac{1}{4}p^2+O(n) =\frac{1}{4}n^2+O(n). $$

Conclusion

Placing all symmetric variables consecutively forces a single quadratic DP in the sum variable constrained to two target levels, yielding

$$ B(f^\pi)=\frac{1}{3}n^2+O(n), $$

while splitting them between the beginning and end reduces each DP width to about half, producing two independent quadratic contributions and

$$ B(f^\pi)=\frac{1}{4}n^2+O(n). $$

This completes the proof. ∎

TAOCP 7.1.4 Exercise 159