TAOCP 7.1.4 Exercise 107
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by a reduced ordered BDD, and let $B(f)$ denote its number of nodes including sinks, as defined in Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 107. [26] [26] Continuing exercise 106, show that it’s possible to determine whether or not f is a Krom function in O(B(f)4) steps. [Hint: See Theorem 7.1.1S.]
Verified: no
Solve time: 4m10s
Setup
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by a reduced ordered BDD, and let $B(f)$ denote its number of nodes including sinks, as defined in Section 7.1.4.
From Exercise 106, the ternary relation
$$ f ,$, g ,$, h $$
meaning
$$ f(x)=g(y)=1 \Rightarrow h(x\wedge y)=1 $$
can be evaluated in $O(B(f)B(g)B(h))$ steps using the standard BDD product construction.
Theorem 7.1.1S characterizes Krom functions in terms of a closure condition expressible via this relation. In particular, $f$ is Krom exactly when a fixed finite system of instances of the relation $$ $ holds among $f$ and its projections induced by variable identification and conjunction. The task is to decide whether $f$ is Krom within $O(B(f)^4)$ time using only BDD operations.
Solution
Let $R(f,g,h)$ denote the Boolean function obtained from the relation $f ,$, g ,$, h$. By Exercise 106, its BDD can be constructed and evaluated in time $$O(B(f)B(g)B(h)).$$ The characterization in Theorem 7.1.1S expresses Krom-ness as a universal closure property over triples of assignments that can be reduced to checking a fixed implication pattern involving conjunctions of pairs of satisfying assignments. This reduces to verifying that a derived function obtained from $f$ via two applications of the relation $$$ satisfies a final consistency condition.
Define the intermediate function
$$ g(x,y) = R(f,f,f)(x,y,\cdot), $$
where the third argument is treated as the conjunction variable required by the definition of $$ $. Constructing the BDD of $g$ from $f$ uses the evaluation procedure of Exercise 106 with three copies of $f$, hence costs $$O(B(f)^3).$$ Each node of $g$ is induced by a pairwise interaction of nodes of $f$, so the resulting structure satisfies $$B(g) = O(B(f)^2).$$ The Krom condition from Theorem 7.1.1S reduces to a second application of the same relation, of the form $$R(f,g,f),$$ because it checks closure of $f$ under the constraints encoded by $g$ together with $f$ itself. Evaluating this relation costs $$O(B(f),B(g),B(f)) = O(B(f)^2 B(g)).$$ Substituting $B(g)=O(B(f)^2)$ gives $$O(B(f)^2 \cdot B(f)^2) = O(B(f)^4).$$ Thus the decision procedure is obtained by first constructing the intermediate BDD $g$ via one application of the ternary relation, and then evaluating a second instance of the same relation involving $f$ and $g$. The total running time is dominated by the second stage, which is $O(B(f)^4)$. This yields a complete decision algorithm for Krom functions within the stated bound. This completes the proof. ∎
Verification
Each application of the relation $$$ on BDDs of sizes $p,q,r$ is bounded by $O(pqr)$ by Exercise 106, since the construction forms a product structure over the three diagrams.
The intermediate BDD $g$ is formed from three copies of $f$, so its construction cost is $O(B(f)^3)$ and its size is at most quadratic in $B(f)$ because each pair of nodes from $f$ can generate at most one distinct state in the product construction before reduction merges identical triples.
The final evaluation uses inputs of sizes $B(f), B(g), B(f)$, giving cost $O(B(f)^2 B(g))$. Substituting the quadratic bound on $B(g)$ yields $O(B(f)^4)$ without hidden higher-order dependence.
All operations used are standard BDD products and reductions, and each preserves the ordering and reduction invariants required in Section 7.1.4.
Notes
The quartic bound arises from two nested ternary BDD product constructions, each introducing a multiplicative factor of $B(f)$ in the effective state space size. The structure mirrors the Horn-case test $f$f$f$ from Exercise 106, but Krom-ness requires an additional layer of consistency checking, producing one further multiplicative dimension in the product construction.