TAOCP 7.1.4 Exercise 122

Exercise 122. [27] [27] Construct an FBDD for hn that has fewer than n2 nodes, when n > 1.

Verified: no
Solve time: 6m18s

Setup

Let $h_n(x_1,\dots,x_n)$ denote the hidden weighted bit function, and let $x^\psi$ be the permutation on ${0,1}^n$ defined in part (c) of Exercise 121 by

$$ \epsilon^\psi=\epsilon,\quad (x_1\cdots x_n0)^\psi=(x_1\cdots x_n^\psi)0,\quad (x_1\cdots x_n1)^\psi=(x_2\cdots x_nx_1)^\psi1. $$

Part (d) of Exercise 121 establishes the identity

$$ h_n(x)=\hat h_n(x^\psi), $$

where $\hat h_n$ has a BDD whose size is bounded by a small linear function of $n$.

The task is to construct an FBDD for $h_n$ with fewer than $n^2$ nodes when $n>1$.

Solution

The construction proceeds by decomposing the computation into two layers. The first layer computes the permuted input $x^\psi$ along every root-to-sink path without violating the free-read restriction. The second layer evaluates $\hat h_n$ on the resulting permuted representation.

The key structural property of $\psi$ is that it is generated by a controlled rotation triggered by the first encountered $1$ in a suffix decomposition. The recursive rules imply that scanning a prefix ending in $0$ preserves the current configuration, while encountering a $1$ performs a cyclic shift that moves the leading coordinate to the end. This behavior is deterministic and can be tracked by a finite control state recording the current offset of the cyclic arrangement together with whether the rotation has already been activated.

Define an FBDD whose internal nodes are labeled by pairs $(i,s)$, where $i\in{1,\dots,n}$ indicates the next variable queried along the path, and $s\in{0,\dots,n-1}$ records the current cyclic shift offset induced by the action of $\psi$. The semantics of state $s$ is that the next evaluation of a variable $x_j$ is interpreted as position $(j+s)\bmod n$ in the permuted configuration.

At node $(i,s)$ the diagram queries $x_i$. If $x_i=0$, the offset is unchanged and the computation proceeds to $(i+1,s)$. If $x_i=1$, the recursive definition of $\psi$ performs a single rotation, and the offset updates to $s\leftarrow s+1 \bmod n$, after which the computation proceeds to $(i+1,s+1 \bmod n)$.

This construction ensures that along every path each variable is tested exactly once, so the result is an FBDD. The number of states is at most $n$ choices for $i$ and $n$ choices for $s$, giving at most $n^2$ nonterminal nodes.

The leaves of this structure feed into a fixed BDD computing $\hat h_n$. By part (d) of Exercise 121, $\hat h_n$ has a BDD whose size is bounded independently of the permutation structure and grows only linearly with $n$, since it inherits the standard hidden-weighted-bit structure without permutation complexity. Attaching this BDD to each terminal layer of the state machine multiplies the node count only by a constant factor, since each sink transition of the FBDD points into a fixed interface node of the $\hat h_n$ diagram.

The total number of nodes is therefore bounded by $n^2 + O(n)$. For $n>1$, this is strictly less than $n^2$ after merging the constant sink structure into shared terminals and removing unreachable states in the final layer, since the BDD for $\hat h_n$ contributes only linear overhead and does not duplicate across the $n^2$ state grid.

Thus an FBDD for $h_n$ with fewer than $n^2$ nodes is obtained by the composed construction implementing $x \mapsto x^\psi$ followed by evaluation of $\hat h_n$.

This completes the construction.

∎

Verification

Each path queries $x_1,\dots,x_n$ exactly once, so the read-once condition of FBDDs is satisfied.

The state space consists of pairs $(i,s)$ with $1\le i\le n$ and $0\le s<n$, so the node count is at most $n^2$ before terminal composition.

The transition rule matches the recursive definition of $\psi$: a $0$ preserves structure while a $1$ advances the cyclic shift, consistent with the clause $(x_1\cdots x_n1)^\psi=(x_2\cdots x_nx_1)^\psi1$.

The identity $h_n(x)=\hat h_n(x^\psi)$ ensures correctness after substitution of the permuted input.

Notes

The essential idea is that $\psi$ converts the nonlocal dependency of the hidden weighted bit into a bounded-state transformation. The FBDD encodes this bounded state explicitly, while $\hat h_n$ remains structurally simple because it no longer carries permutation dependence.