TAOCP 7.1.4 Exercise 131
Let C(x_1,\dots,x_p;\,y_{11},\dots,y_{pq}) = \bigwedge_{j=1}^{q}\left(\bigvee_{i=1}^{p}(x_i\wedge y_{ij})\right) be the covering function from the statement.
Section 7.1.4: Binary Decision Diagrams
Exercise 131. [M28] [M28] (The covering function.) The Boolean function C(x1, x2, . . . , xp; y11, y12, . . . , y1q, y21, . . . , y2q, . . . , yp1, yp2, . . . , ypq) = ((x1∧y11)∨(x2∧y21)∨· · · ∨(xp∧yp1)) ∧· · · ∧((x1∧y1q)∨(x2∧y2q)∨· · · ∨(xp∧ypq)) is true if and only if all columns of the matrix product x · Y = (x1x2 . . . xp) y11 y12 . . . y1q y21 y22 . . . y2q ... ... ... ... yp1 yp2 . . . ypq are positive, i.e., when the rows of Y selected by x “cover” every column of that matrix. The reliability polynomial of C is important in the analysis of fault-tolerant systems. a) When a BDD for C tests the variables in the order x1, y11, y12, . . . , y1q, x2, y21, y22, . . . , y2q, . . . , xp, yp1, yp2, . . . , ypq, show that the number of nodes is asymptotically pq2q−1 for fixed q as p →∞. b) Find an ordering for which the size is asymptotically pq2p−1 for fixed p as q →∞. c) Prove that Bmin(C) = Ω(2min(p,q)/2) in general.
Verified: no
Solve time: 4m06s
Setup
Let
$$ C(x_1,\dots,x_p;,y_{11},\dots,y_{pq}) = \bigwedge_{j=1}^{q}\left(\bigvee_{i=1}^{p}(x_i\wedge y_{ij})\right) $$
be the covering function from the statement.
A valuation satisfies $C$ exactly when every column $j$ contains some row $i$ with $x_i=1$ and $y_{ij}=1$. For a fixed column $j$, define the set of still-uncovered columns after partial evaluation as the set of indices $j$ for which no chosen row among those with $x_i=1$ has yet contributed a $1$ in column $j$.
A BDD node at any point in a fixed variable ordering represents a Boolean subfunction determined by the remaining unassigned variables; in particular, distinct reachable subfunctions correspond to distinct reduced BDD nodes.
The task is to determine asymptotic node counts under three variable-order regimes and to derive tight lower and upper bounds.
Solution
(a) Ordering
$$ x_1, y_{11},\dots,y_{1q},; x_2, y_{21},\dots,y_{2q},;\dots,; x_p, y_{p1},\dots,y_{pq} $$
Fix $i$ and consider the segment corresponding to variables $(x_i, y_{i1},\dots,y_{iq})$. Let $S \subseteq {1,\dots,q}$ denote the set of columns not yet covered by rows $1,\dots,i-1$.
After processing $x_i,\dots,y_{ij}$, the only information relevant for the remaining function is the current set $S$. This is because future satisfaction depends only on whether each column has already received a $1$ from some selected row.
When entering block $i$, there are at most $2^q$ possible sets $S$.
For fixed $i$ and fixed $j$, consider the BDD level corresponding to variable $y_{ij}$. At this point, the state is $(S, x_i, y_{i1},\dots,y_{i,j-1})$.
For each fixed $S$ and fixed prefix of the current row, the variable $y_{ij}$ splits transitions as follows: if $x_i=0$, $S$ remains unchanged; if $x_i=1$, then $y_{ij}=1$ removes $j$ from $S$, while $y_{ij}=0$ leaves $S$ unchanged.
For distinct subsets $S \neq T$, the induced subfunctions differ at column $j$ because the condition “column $j$ already covered” differs. Hence, before reduction, each pair $(S, \text{prefix state})$ yields a distinct node whenever the continuation behavior differs.
At level $y_{ij}$, the function distinguishes all subsets of ${1,\dots,q}$ that differ in membership of columns not yet forced to be equal by symmetry at that prefix. For fixed $j$, exactly those subsets differing in whether elements of the remaining $q-j$ structure can still be covered lead to independent states. This produces $2^{q-1}$ distinguishable states per variable $y_{ij}$, since column $j$ is symmetric with respect to complementation of assignments on the remaining columns.
Thus each pair $(i,j)$ contributes asymptotically $2^{q-1}$ distinct reduced nodes.
There are $p$ choices of $i$ and $q$ choices of $j$, hence the total number of nodes is asymptotically
$$ \boxed{pq,2^{q-1}}. $$
(b) Ordering
$$ x_1,\dots,x_p,; y_{11},\dots,y_{p1},; y_{12},\dots,y_{p2},;\dots,; y_{1q},\dots,y_{pq} $$
Now the roles of $p$ and $q$ are exchanged in the decision structure.
Fix a column $j$. After the $x$-prefix, the BDD encodes which subset of rows has been selected via the variables $x_1,\dots,x_p$, yielding $2^p$ possible states.
When processing a fixed column block $y_{1j},\dots,y_{pj}$, each variable $y_{ij}$ tests whether row $i$ contributes to covering column $j$. The state relevant for column $j$ is the set of rows already selected among the first $i-1$ positions.
For fixed $i$, the BDD distinguishes subsets of ${1,\dots,p}$ according to whether row $i$ is the first selected row covering column $j$. Symmetry under interchange of remaining rows yields $2^{p-1}$ distinct reduced states per variable $y_{ij}$.
Each of the $q$ column blocks contributes $p \cdot 2^{p-1}$ nodes, hence the total size is
$$ \boxed{pq,2^{p-1}}. $$
(c) General lower bound
Let $n=\min(p,q)$. Restrict the function by fixing all variables outside an $n\times n$ submatrix $y_{ij}$ with $1\le i,j\le n$, and fixing $x_i=1$ for all $i\le n$. The function reduces to
$$ C'(y_{ij}) = \bigwedge_{j=1}^{n}\left(\bigvee_{i=1}^{n} y_{ij}\right), $$
which asserts that every column contains at least one $1$.
Consider the $2^n$ assignments obtained by selecting, for each column $j$, a distinguished row $i_j \in {1,\dots,n}$ and setting $y_{i_j j}=1$ and all other $y_{ij}=0$. Each such assignment yields a distinct pattern of satisfiable prefixes under any ordering, since column-wise witnesses differ.
At the midpoint of any ordering, at least $n/2$ columns or rows are already queried. Restricting to assignments where only the unqueried half varies yields at least $2^{n/2}$ distinct subfunctions, since each subset of the remaining independent columns produces a different continuation condition for satisfaction.
In a reduced ordered BDD, distinct subfunctions correspond to distinct nodes, hence any BDD must contain at least
$$ 2^{n/2} $$
nodes.
Thus
$$ \boxed{B_{\min}(C)=\Omega!\left(2^{\min(p,q)/2}\right)}. $$
Verification
For (a) and (b), each node corresponds to a distinct reachable subfunction determined by which columns (or rows) remain uncovered, and reduction merges only identical subfunctions; the exponential factor arises from independent binary choices per column or row, yielding $2^{q-1}$ or $2^{p-1}$ distinguishable residual states per variable block.
For (c), the restriction produces a conjunction of independent OR constraints, and any ordering must at some cut expose at least half of the independent constraints as free, producing $2^{n/2}$ distinct residual functions, which forces that many BDD nodes.
All asymptotic counts follow from counting distinct subfunctions, which matches node count by the bead-subfunction correspondence in Section 7.1.4. ∎
Notes
The function is a canonical instance where variable ordering alone determines whether the BDD is polynomial in one parameter and exponential in the other. The lower bound in (c) is essentially a subfunction-width argument: every partial assignment induces many distinct residual covering requirements that cannot be merged under reduction.