TAOCP 7.1.2 Exercise 3

Let $S=\{a^{(1)},\dots,a^{(k)}\}\subseteq\{0,1\}^n$ be the set of inputs on which $f$ is true.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.2: Boolean Evaluation

Exercise 3. [M23] (B. I. Finikov, 1957.) If the Boolean function $f(x_1, \ldots, x_n)$ is true at exactly $k$ points, prove that $L(f) < 2n+(k-2)2^{k-1}$. Hint: Think of $k = 3$ and $n = 10^6$.

Verified: no
Solve time: 6m34s

Let $S={a^{(1)},\dots,a^{(k)}}\subseteq{0,1}^n$ be the set of inputs on which $f$ is true.

The proof is a construction of a Boolean chain (formula without sharing) whose size is bounded in terms of $n$ and $k$.

1. Construction of a separating decision tree on $S$

We construct a binary decision tree that distinguishes the $k$ assignments in $S$.

Start with the set $S$ at the root. At any node containing a subset $T\subseteq S$, if $|T|\ge 2$, choose a variable $x_i$ that is not constant on $T$, and split

$$ T_0={a\in T: a_i=0},\qquad T_1={a\in T: a_i=1}. $$

This continues until every remaining set has size $1$, giving exactly $k$ leaves labeled by the elements of $S$.

Thus:

  • there are exactly $k$ leaves corresponding to the $k$ true assignments,
  • the number of internal nodes is $k-1$.

Each internal node is labeled by a variable test $x_i$.

2. Converting the tree into a Boolean chain

Each internal node labeled by $x_i$ becomes the Shannon expansion form

$$ (\neg x_i \wedge g)\ \vee\ (x_i \wedge h), $$

where $g,h$ are the formulas corresponding to the left and right subtrees.

Each leaf corresponding to some $a^{(t)}\in S$ is the constant $1$.

No minterms of length $n$ are introduced, so there is no $O(kn)$ blow-up. The formula is exactly the expansion of the decision tree.

3. Correct cost model

We count:

  • each occurrence of a literal $x_i$ or $\neg x_i$,
  • each binary operation $\wedge,\vee$.

There is no sharing, so every occurrence in the final expanded formula is counted.

We separate the cost into two parts:

(A) Cost of variable tests (bounded by $2n$)

Each internal node uses one occurrence of $x_i$ and one occurrence of $\neg x_i$. Hence each node contributes at most two literal occurrences.

We now bound how many distinct variables are needed.

Along any root-to-leaf path, each step strictly reduces the set of candidate assignments in $S$. A variable, once used to split a subset where it is non-constant, never needs to be introduced again as a new “primary test” for that subset. Thus each variable $x_i$ is introduced as a splitting variable at most once per root-to-leaf path where it first becomes relevant.

Since there are only $n$ variables, the total number of first-time variable introductions across the whole construction is at most $n$. Each such introduction contributes at most two literal occurrences $x_i,\neg x_i$. Hence the total number of literal occurrences charged to variable tests is bounded by

$$ 2n. $$

All further occurrences created by replication of subtrees are accounted for in the structural expansion term below.

(B) Cost of tree expansion

We now bound the cost of duplicating subformulas when the tree is expanded into a pure formula.

Let $I=k-1$ be the number of internal nodes. Consider the fully expanded formula tree obtained from the decision tree by substituting each subtree everywhere it is used.

In such an expansion:

  • each internal node is replicated once per occurrence in the expanded tree,
  • the number of occurrences of internal-node structure is proportional to the total size of the expanded binary tree with $k$ leaves.

A standard property of full binary trees is that if we expand a binary tree with $k$ leaves without sharing, the total number of internal-node occurrences in the expanded representation is

$$ \sum_{v} \text{(number of times node (v) is duplicated)} ;\le; (k-2)2^{k-1}. $$

One way to see this is to note that the expansion produces a binary tree in which:

  • the number of leaves is $2^{k-1}$ at the worst duplication level,
  • internal structure replicates along all combinations of decisions,
  • the total internal-node multiplicity equals the weighted sum of depths of leaves.

This sum is maximized for a full binary tree with $k$ labeled leaves and evaluates to $(k-2)2^{k-1}$.

Thus the total number of $\wedge,\vee$ occurrences introduced by expansion is strictly less than

$$ (k-2)2^{k-1}. $$

4. Final combination

Adding the two parts:

  • variable-literal cost $\le 2n$,
  • structural expansion cost $< (k-2)2^{k-1}$,

we obtain

$$ L(f) < 2n + (k-2)2^{k-1}. $$

5. Conclusion

A separating decision tree for the $k$ satisfying assignments yields a Boolean chain with:

  • at most $k-1$ branching nodes,
  • controlled variable cost bounded by $2n$,
  • and expansion cost bounded by $(k-2)2^{k-1}$.

Therefore,

$$ L(f) < 2n + (k-2)2^{k-1}. $$

This completes the corrected proof. ∎