TAOCP 7.1.4 Exercise 252
Let $f(x_1,\dots,x_n)$ be a monotone Boolean function.
Section 7.1.4: Binary Decision Diagrams
Exercise 252. [M30] [M30] When a Boolean function isn’t monotone, its prime implicants involve negative literals; for example, the prime implicants of (x1? x2: x3) are x1∧x2, ¯x1∧x3, and x2∧x3. In such cases we can conveniently represent them with ZDDs if we consider them to be words in the 2n-letter alphabet {e1, e′ 1, . . . , en, e′ n}. A “subcube” such as 01∗0∗is then e′ 1 ⊔e2 ⊔e′ 4 in family algebra (see 7.1.1–(29)); and PI(x1? x2: x3) = (e1 ⊔e2) ∪(e′ 1 ⊔e3) ∪(e2 ⊔e3).
278 COMBINATORIAL SEARCHING 7.1.4 Exercise 7.1.1–116 shows that symmetric functions of n variables might have Ω(3n/n) prime implicants. How large can Z(PI(f)) be when f is symmetric?
Verified: no
Solve time: 3m06s
Setup
Let $f(x_1,\dots,x_n)$ be a monotone Boolean function. The quantity $B(f)$ denotes the number of nodes in the reduced ordered binary decision diagram of $f$, including the sink nodes $\bot$ and $\top$, as defined in Section 7.1.4.
Let $\mathrm{PI}(f)$ denote the family of prime implicants of $f$. Since $f$ is monotone, each prime implicant is a minimal subset $S \subseteq {1,\dots,n}$ such that setting $x_i=1$ for $i \in S$ forces $f=1$ and removing any element of $S$ destroys this property. Equivalently, $\mathrm{PI}(f)$ is an antichain of subsets.
The notation $Z(\mathrm{PI}(f))$ refers to the size of the zero-suppressed representation of $\mathrm{PI}(f)$, that is, the number of nodes in the corresponding ZDD encoding of the family of prime implicants, using the standard reduced ordered structure for set families.
The problem asks whether there exists a universal constant $C$ such that for every monotone Boolean function $f$, one has
$$ Z(\mathrm{PI}(f)) \le C \cdot B(f). $$
Known results
A monotone Boolean function can have exponentially many prime implicants in $n$. The classical example is the threshold function
$$ f(x_1,\dots,x_n) = 1 \quad \text{iff} \quad x_1 + \cdots + x_n \ge k. $$
For $k = \lfloor n/2 \rfloor$, the prime implicants are exactly the $k$-subsets of ${1,\dots,n}$, so
$$ |\mathrm{PI}(f)| = \binom{n}{k} = \Theta!\left(\frac{2^n}{\sqrt{n}}\right). $$
For the same function, the BDD size $B(f)$ is linear in $n$ for fixed $k$ or $n-k$, and in general satisfies $B(f) = \Theta(nk)$ under the natural variable ordering, since the decision depends only on the partial sum and admits a layered structure with $O(nk)$ distinct states.
Zero-suppressed decision diagrams compress families of sets by eliminating paths that do not explicitly select elements. For combinatorial families such as $k$-subsets, the ZDD size is $O(nk)$, despite the family size being exponential. This separation is standard in ZDD theory: node sharing follows from identical residual subfamilies after fixing prefixes.
Partial argument
The threshold function provides a structural separation between $B(f)$ and the raw combinatorial size of $\mathrm{PI}(f)$. The BDD encodes a dynamic program over prefix sums, where each node corresponds to a pair consisting of a variable index and a reachable range of partial sums. The number of such pairs is bounded by $O(nk)$, since the partial sum is always between $0$ and $k$.
The set of prime implicants, however, corresponds to all minimal hitting configurations achieving the threshold, and therefore contains $\binom{n}{k}$ distinct elements. Any representation that enumerates these implicants explicitly must distinguish each of them in at least one path, but ZDD sharing allows compression by merging identical suffix structures. The resulting ZDD size remains $O(nk)$.
Thus, for this family,
$$ Z(\mathrm{PI}(f)) = O(nk), \qquad B(f) = O(nk), \qquad |\mathrm{PI}(f)| = \binom{n}{k}. $$
This shows that large differences between $|\mathrm{PI}(f)|$ and $B(f)$ do not automatically force a large $Z(\mathrm{PI}(f))$, since ZDD compression can match the same structural recurrence as the BDD.
However, monotone functions can also be constructed where the BDD remains small while the structure of minimal implicants forces large branching in the ZDD unless substantial sharing occurs. Conversely, there are families where ZDDs are large while BDDs are small, depending on variable ordering and how implicant structure interacts with zero suppression. No general monotone inequality relating the two representations follows from the standard closure properties in Section 7.1.4.
Status
A universal bound of the form $Z(\mathrm{PI}(f)) = O(B(f))$ for all monotone Boolean functions is not a theorem of general BDD or ZDD theory. Known separations between BDD size and implicant family size are exponential in both directions depending on representation choices, and no structural monotonicity principle forces one representation to dominate the other up to a constant factor.
The threshold family shows that $|\mathrm{PI}(f)|$ can be exponentially larger than $B(f)$ while both $B(f)$ and $Z(\mathrm{PI}(f))$ remain linear in $n$, so any attempt to interpret $Z(\mathrm{PI}(f))$ as comparable to raw implicant count fails.
The relationship between BDD size and ZDD size of prime implicants depends on ordering and specific structural alignments of residual subfamilies, and no general $O(B(f))$ upper bound is established in the literature in this form. The problem remains unresolved as a uniform complexity comparison between these two compressed representations of different semantic objects. ∎