TAOCP 7.1.4 Exercise 114

Exercise 114. [20] [20] Is there a function with profile (1,1,1,1,1,2) and quasi-profile (1,2,3,4,3,2)?

Verified: no
Solve time: 2m56s

Setup

Let the function depend on six variables $x_1,\dots,x_6$.

The profile $(p_1,p_2,p_3,p_4,p_5,p_6)$ denotes the number of distinct BDD nodes (beads) at levels $1$ through $6$, where level $k$ corresponds to subfunctions of the form $f(x_k,\dots,x_6)$.

The quasi-profile $(q_1,q_2,q_3,q_4,q_5,q_6)$ denotes the number of distinct subtables generated before reduction at each level, so each node at level $k-1$ contributes at most two subtables at level $k$.

The question asks whether there exists a Boolean function whose profile is

$$ (p_1,p_2,p_3,p_4,p_5,p_6)=(1,1,1,1,1,2) $$

and whose quasi-profile is

$$ (q_1,q_2,q_3,q_4,q_5,q_6)=(1,2,3,4,3,2). $$

Solution

At level $k-1$, each BDD node labeled by $x_{k-1}$ has exactly two outgoing arcs, LO and HI, producing two subtables at level $k$. Therefore every node at level $k-1$ contributes at most two (not necessarily distinct) subtables at level $k$.

This yields the fundamental constraint

$$ q_k \le 2p_{k-1} \quad\text{for } k \ge 2, $$

since $p_{k-1}$ is the number of nodes available to generate subtables at level $k-1$.

Now substitute the given profile and quasi-profile values at level $k=3$:

$$ p_2 = 1, \quad q_3 = 3. $$

The branching constraint gives

$$ q_3 \le 2p_2 = 2. $$

This contradicts the specified value $q_3 = 3$.

Since the constraint follows directly from the definition of BDD branching, no function can realize both sequences simultaneously.

Therefore no Boolean function exists with the given profile and quasi-profile.

This completes the proof. ∎

Verification

Each level-$k$ subtable arises from choosing either LO or HI edge from a level-$(k-1)$ node. A level-$(k-1)$ node produces at most two level-$k$ subtables, so the total number of distinct level-$k$ subtables cannot exceed $2p_{k-1}$. The violation occurs already at $k=3$, so no further structure can repair consistency.

Answer

$$ \boxed{\text{No such function exists.}} $$