TAOCP 7.1.4 Exercise 106

Let variables of $f$ be $x_1,\dots,x_n$, variables of $g$ be $y_1,\dots,y_n$, and variables of $h$ be $z_1,\dots,z_n$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 106. [25] [25] Let f $g$h denote the relation “f(x) = g(y) = 1 implies h(x∧y) = 1, for all x and y.” Show that this relation can be evaluated in at most O(B(f)B(g)B(h)) steps. [Motivation: Theorem 7.1.1H states that f is a Horn function if and only if f $f $f; thus we can test Horn-ness in O(B(f)3) steps.]

Verified: no
Solve time: 4m10s

Solution

Let variables of $f$ be $x_1,\dots,x_n$, variables of $g$ be $y_1,\dots,y_n$, and variables of $h$ be $z_1,\dots,z_n$. The relation $f , $, g , $, h$ holds exactly when

$$ \forall x \in {0,1}^n ;\forall y \in {0,1}^n:; (f(x)=1 \wedge g(y)=1) \Rightarrow h(x \wedge y)=1, $$

where $(x \wedge y)_i = x_i \wedge y_i$.

This condition fails exactly when there exist $x,y$ such that

$$ f(x)=1,\quad g(y)=1,\quad h(x \wedge y)=0. $$

Hence the relation holds if and only if the Boolean function

$$ F(x,y) = f(x)\wedge g(y)\wedge \neg h(x \wedge y) $$

is identically $0$.

The task is to evaluate whether the BDD of $F$ contains any satisfying assignment.

Construction of $h(x \wedge y)$

Define a function $h^\wedge(x,y)=h(x \wedge y)$ over variables $(x_1,y_1,\dots,x_n,y_n)$. Construct a BDD for $h^\wedge$ from the BDD of $h$ by replacing each test on $z_i$ with a test on the pair $(x_i,y_i)$ using the identity

$$ z_i = x_i \wedge y_i. $$

Each branch node of $h$ labeled $z_i$ is replaced by a constant-size gadget that first tests $x_i$, and only if $x_i=1$ proceeds to test $y_i$; the resulting HI branch is taken exactly when both are $1$. The LO branch is taken otherwise. This replacement preserves ordering since both $x_i$ and $y_i$ occur before any variable with index $>i$ in the induced ordering. Reduction introduces no blow-up beyond a constant factor per node. The resulting BDD has size $O(B(h))$.

Denote this BDD by $H$.

Complementation

Construct $\neg H$ by swapping sink nodes $\top$ and $\bot$ in $H$. This does not change the number of nodes, so the size remains $O(B(h))$.

Construction of the conjunction

Let $F_0(x)=f(x)$ viewed as a BDD over variables $x_1,\dots,x_n$, and let $G_0(y)=g(y)$ over variables $y_1,\dots,y_n$. These two BDDs are defined on disjoint variable sets, so the standard APPLY operation for BDD conjunction yields a BDD for

$$ F_1(x,y)=f(x)\wedge g(y). $$

The APPLY algorithm on ordered reduced BDDs performs one recursive call per pair of nodes, so its complexity is proportional to the product of the sizes of the inputs. Hence the construction of $F_1$ requires

$$ O(B(f),B(g)) $$

steps.

The resulting BDD satisfies

$$ B(F_1) \le B(f),B(g) $$

since each reachable pair of nodes contributes at most one node in the product construction.

Final conjunction with $\neg h(x \wedge y)$

Now compute

$$ F(x,y)=F_1(x,y)\wedge \neg H(x,y). $$

Applying APPLY again yields a BDD for $F$ with cost proportional to the product of the sizes of its arguments:

$$ O(B(F_1),B(H)). $$

Using $B(F_1)\le B(f)B(g)$ and $B(H)=O(B(h))$, this step costs

$$ O(B(f),B(g),B(h)). $$

Decision step

The relation $f , $, g , $, h$ holds if and only if the BDD for $F$ is the constant $\bot$. Testing whether a BDD is identically $\bot$ requires checking whether the root is the sink $\bot$, which is constant time once the BDD is constructed.

Complexity bound

The construction of $H$ costs $O(B(h))$, the construction of $F_1$ costs $O(B(f)B(g))$, and the final conjunction costs $O(B(f)B(g)B(h))$. The last term dominates, so the total time is

$$ O(B(f)B(g)B(h)). $$

This completes the proof. ∎