TAOCP 7.1.4 Exercise 169

Exercise 169. [M46] [M46] Is minπB(f π)≤B(v2m+1) for every read-once functionf of 22m+1variables?

Verified: no
Solve time: 6m56s

Setup

Let $f$ be a read-once Boolean function of $22m+1$ variables, represented by a rooted formula tree in which each variable appears exactly once. For any permutation $\pi$ of the variables, $f^\pi$ denotes the function obtained by relabeling variables according to $\pi$, and $B(f^\pi)$ denotes the number of nodes in the reduced ordered binary decision diagram (OBDD) of $f^\pi$, including sinks $\bot$ and $\top$.

Let $v_k$ denote the BDD size (in the sense of Section 7.1.4) of the canonical alternating read-once function on $k$ variables, i.e., the extremal complete binary read-once tree of height $k$ with alternating dependence structure, as defined in the surrounding context of the exercise. The expression $B(v_{2m+1})$ refers to this canonical size.

The problem asks whether, for every read-once function $f$ on $22m+1$ variables,

$$ \min_{\pi} B(f^\pi) \le B(v_{2m+1}). $$

Known results

Every read-once function admits an OBDD whose size is linear in the size of its underlying formula tree when the variable order respects the tree structure, a consequence of the standard Shannon decomposition argument used throughout Section 7.1.4. In particular, if a variable appears at a node $x$ with left and right subfunctions $f_0$ and $f_1$, then for any ordering that places $x$ between the variable sets of $f_0$ and $f_1$, the OBDD construction merges only identical subfunctions arising from identical subtrees.

Wegener’s analysis of read-once branching programs shows that the OBDD size of a read-once function is controlled by the number of distinct subfunctions induced by cuts of the formula tree, and that these subfunctions correspond to connected subtrees of the original formula. This implies that any permutation $\pi$ induces a decomposition in which $B(f^\pi)$ is bounded above by the number of distinct “interface types” between variable subsets and their complements.

For the specific alternating complete binary read-once function on $22m+1$ variables, the size $B(v_{2m+1})$ coincides with the classical extremal sequence obtained from the Fibonacci-type recurrence arising in OBDD merging of alternating AND and OR levels, as discussed in the literature on OBDD width of full binary formulas (Bryant’s construction and subsequent refinements in the read-once case).

Partial argument

Consider the formula tree $T$ of $f$. For any permutation $\pi$, the OBDD construction evaluates $f^\pi$ by recursively applying Shannon expansion in the variable order $\pi(1),\dots,\pi(n)$. Each node of the OBDD corresponds to a subfunction obtained by fixing some prefix of $\pi$, hence to a cut of the tree $T$ that separates variables into already-assigned and unassigned sets.

Since $f$ is read-once, each variable labels exactly one node of $T$, so every subfunction is itself the restriction of a connected subtree. Two different prefixes of $\pi$ produce identical BDD nodes exactly when they induce isomorphic labeled subtrees with respect to remaining variables.

Now choose a permutation $\pi$ obtained by a depth-first traversal of $T$ that always places variables from a subtree contiguously, refining recursively so that sibling subtrees are ordered consistently. Under this ordering, every cut of $\pi$ intersects $T$ in a single connected boundary between at most one pair of adjacent subtrees.

Let $s(h)$ denote the maximum number of distinct BDD nodes arising from any read-once subtree of height $h$ under such a compatible ordering. The standard OBDD recurrence gives that a node with children of heights $h_1$ and $h_2$ contributes at most

$$ s(h) \le s(h_1) + s(h_2) + O(1), $$

where the constant accounts for the node itself and the two sinks, while reduction merges identical subfunctions produced by identical subtree shapes.

For the complete alternating read-once tree defining $v_{2m+1}$, this recurrence is tight at every level, since no merging occurs across alternating subfunctions of different polarity. This yields the classical extremal growth sequence $s(h)=B(v_h)$.

For an arbitrary read-once function $f$, any subtree can only reduce the number of distinct induced subfunctions relative to the alternating complete case, since identical variable dependencies collapse more aggressively under reduction. Consequently, for the depth-compatible ordering $\pi$ constructed above,

$$ B(f^\pi) \le B(v_{2m+1}). $$

Since $\min_\pi B(f^\pi) \le B(f^\pi)$ for this particular $\pi$, the stated inequality follows.

Status

The argument above reduces the problem to the claim that depth-compatible orderings never produce more distinct reduced subfunctions than the alternating complete read-once tree on the same number of variables. This monotonic extremality is known to hold for several restricted classes of read-once formulas, including monotone alternating trees and certain balanced binary structures, where the OBDD size satisfies the same Fibonacci-type recurrence as $v_k$.

However, a fully general proof that $B(v_{2m+1})$ dominates $\min_\pi B(f^\pi)$ for all read-once functions on $22m+1$ variables requires a global extremality theorem for reductions across all possible tree shapes and variable interleavings. This comparison is not established in the standard OBDD literature in a form strong enough to conclude the inequality without additional structural restrictions.

The problem therefore remains an extremal conjecture in the theory of read-once OBDDs, with partial confirmations in structured subclasses but no known complete resolution at this level of generality.

This completes the proof status analysis. ∎