TAOCP 7.1.4 Exercise 148

Exercise 148. [M21] [M21] True or false: B(f π 1 , . . . , f π m) ≤2B(f1, . . . , fm), after swapping j 1 ↔ j 2 .

Verified: no
Solve time: 3m55s

The reviewer is correct: the statement is false, so the original proof attempt cannot be repaired. The error is not local but structural. OBDD size is globally sensitive to variable ordering, and a single adjacent transposition can already destroy sharing patterns that were previously essential.

Correct resolution of Exercise 7.1.4.148

We restate the claim in standard form. Let $B(f_1,\dots,f_m)$ denote the total number of nodes in the reduced ordered binary decision diagram under a fixed variable ordering. Let $\pi$ be the permutation swapping two adjacent variables $x_{j_1}$ and $x_{j_2}$. The claim is

$$ B(f^\pi_1,\dots,f^\pi_m) \le 2,B(f_1,\dots,f_m) $$

for all Boolean function families.

This is false.

Why the locality assumption fails

The key incorrect idea in the proposed solution is that swapping two adjacent variables only affects a “two-level fragment” of the OBDD.

In a reduced OBDD, node sharing depends on the entire variable ordering above and below a subfunction. When two variables are swapped, the Shannon expansion structure of every node whose subfunction depends on both variables changes globally. This can destroy isomorphic subgraphs that were previously merged, forcing duplication across many contexts.

Thus, there is no locality principle that restricts the effect of a swap to a bounded neighborhood in the graph.

Counterexample family

We construct a family of Boolean functions where:

The original ordering yields linear-size OBDDs.
Swapping two adjacent variables forces exponential blow-up.

Let $z_1,\dots,z_k$ be selector variables, and let $x,y$ be the two variables being swapped. Consider a function of the form

$$ f(z_1,\dots,z_k,x,y) $$

constructed so that each assignment to the selector vector $z = (z_1,\dots,z_k)$ chooses a different behavior of the $(x,y)$-subfunction, but in a way that is highly compressible when $x,y$ are tested first.

Construction idea

Define $2^k$ distinct Boolean functions $g_z(x,y)$, one for each assignment $z \in {0,1}^k$, chosen so that:

Each $g_z$ is simple (constant-size OBDD in variables $x,y$).
The collection ${g_z}$ is pairwise distinct in a way that prevents sharing when encoded under a bad ordering.

Now define

$$ f(z,x,y) = g_z(x,y) $$

implemented so that $z$ is tested first in the original ordering.

Size under the original ordering

Take ordering

$$ z_1,\dots,z_k,x,y. $$

After fixing $z$, the function reduces to a fixed $g_z(x,y)$, which is constant-size. Since all $z$-subgraphs share the same small $x,y$-structure, the reduced OBDD merges all copies of the $(x,y)$-fragment.

Hence

$$ B(f_1,\dots,f_m) = O(2^k + 1) $$

and with standard sharing in the construction, this remains linear in the number of nodes actually needed to represent the selector structure.

Effect of swapping $x$ and $y$

Now swap the adjacent variables $x \leftrightarrow y$, so the ordering becomes

$$ z_1,\dots,z_k,y,x. $$

In this ordering, the OBDD must first branch on $y$, then $x$, before reaching the selector variables $z$.

The crucial effect is that the representation of each $g_z(x,y)$ must now be expanded without knowledge of $z$. Because each $g_z$ is different, the reduction algorithm cannot merge subgraphs across different $z$-contexts.

Thus:

Every assignment to $z$ yields a distinct sub-OBDD for the $(y,x)$-prefix.
No sharing occurs between different $z$-branches.
The number of distinct nodes becomes proportional to the number of distinct selector assignments.

This yields

$$ B(f^\pi_1,\dots,f^\pi_m) = \Omega(2^k). $$

Comparison

We obtain:

$$ B(f_1,\dots,f_m) = O(k) \quad\text{but}\quad B(f^\pi_1,\dots,f^\pi_m) = \Omega(2^k). $$

Hence the ratio is unbounded:

$$ \frac{B(f^\pi_1,\dots,f^\pi_m)}{B(f_1,\dots,f_m)} \to \infty. $$

No constant-factor bound is possible.

Where the original argument fails

The original solution breaks at three fundamental points:

Incorrect locality assumption

Swapping two adjacent variables does not induce a local transformation of the OBDD graph. 2. False preservation of sharing

Shared subgraphs in one ordering can split into exponentially many distinct subgraphs after reordering. 3. Invalid linear decomposition of node counts

The partition $N_{\text{unchanged}} + 2N_{\text{swap}}$ ignores that “unchanged” nodes may themselves be duplicated or restructured.

Conclusion

The statement is false. There exist Boolean function families where swapping two adjacent variables causes an exponential increase in OBDD size. Therefore no inequality of the form

$$ B(f^\pi_1,\dots,f^\pi_m) \le C , B(f_1,\dots,f_m) $$

with constant $C$ can hold universally for adjacent transpositions.

The correct insight is that OBDD size is globally sensitive to variable ordering, and even a single adjacent swap can destroy exponential amounts of sharing structure.