TAOCP 7.1.1 Exercise 103
Let $f:\{0,1\}^n\to\{0,1\}$ be monotone and self-dual, given by its prime implicants $S_1,\dots,S_m\subseteq[n]$.
Exercise 103. [HM25] Explain how to use linear programming to test whether or not a monotone, self-dual Boolean function is a threshold function, given a list of its prime implicants. Also, if it is a threshold function, explain how to minimize the size of its representation as a majority function.
Verified: no
Solve time: 7m12s
Let $f:{0,1}^n\to{0,1}$ be monotone and self-dual, given by its prime implicants $S_1,\dots,S_m\subseteq[n]$. For monotone functions these sets are exactly the minimal 1-sets.
We address the exercise in two parts: (i) LP testing of thresholdness, (ii) minimization of majority representation size.
1. Correct LP formulation for threshold testing
We seek weights $w_i\ge 0$ and threshold $t$ such that
$$ f(x)=1 \iff \sum_{i=1}^n w_i x_i \ge t. $$
1.1 Why minimal 1- and minimal 0-inputs suffice
A key structural fact for monotone Boolean functions is:
- Every 1-input contains a minimal 1-input.
- Every 0-input is contained in a maximal 0-input.
- In a monotone function, maximal 0-inputs are exactly complements of minimal 1-inputs of the dual function $f^\ast(x)=1-f(\bar x)$.
If a linear threshold separation holds for all minimal 1-inputs and all minimal 0-inputs, then it holds for all inputs:
- If $x$ is a 1-input, it contains some minimal 1-set $S_k$, hence $\sum_{i\in x} w_i \ge \sum_{i\in S_k} w_i$.
- If $x$ is a 0-input, it is contained in some maximal 0-set $T_j$, hence $\sum_{i\in x} w_i \le \sum_{i\in T_j} w_i$.
Thus separating these extremal antichains is sufficient and necessary.
1.2 Obtaining minimal 0-inputs
The minimal 0-inputs of $f$ are exactly the complements of minimal 1-inputs of the dual function $f^\ast$, which is also monotone.
Let $T_1,\dots,T_r$ be the prime implicants of $f^\ast$. Then each $T_j$ is a minimal 0-set of $f$.
This equivalence follows from monotone duality:
- prime implicants of $f^\ast$ correspond to minimal assignments forcing $f^\ast=1$,
- equivalently minimal assignments forcing $f=0$.
Thus the set ${T_j}$ is complete for describing all minimal 0-input constraints.
2. Linear programming feasibility system
We now construct the LP.
Variables:
$$ w_1,\dots,w_n \ge 0,\quad t\in\mathbb{R}. $$
Constraints:
2.1 Minimal 1-input constraints
For each prime implicant $S_k$:
$$ \sum_{i\in S_k} w_i \ge t. $$
2.2 Minimal 0-input constraints
For each dual prime implicant $T_j$:
$$ \sum_{i\in T_j} w_i \le t. $$
2.3 Correctness of the LP
If the LP is feasible, define $f'(x)=1$ iff $\sum_i w_i x_i \ge t$.
- Every $x$ containing some $S_k$ satisfies $f'(x)=1$.
- Every $x$ contained in some $T_j$ satisfies $f'(x)=0$.
Because every 1-input contains a minimal 1-input and every 0-input is contained in a minimal 0-input, the function $f'$ agrees with $f$ on all inputs.
Conversely, any threshold representation yields a feasible solution by restricting to minimal 1- and 0-inputs.
Thus feasibility of this LP is equivalent to $f$ being a threshold function.
3. Incorporating self-duality
Self-duality means
$$ f(x)=1-f(\bar x). $$
Let $W=\sum_{i=1}^n w_i$. Consider a threshold representation $w,t$.
For any input $x$,
$$ \sum_{i=1}^n w_i(1-x_i)=W-\sum_{i=1}^n w_i x_i. $$
Self-duality requires that exactly one of $x$ and $\bar x$ is accepted. Therefore the threshold must bisect the total weight:
$$ t=\frac{W}{2}. $$
Justification: if $\sum w_i x_i = t$, then $\sum w_i \bar x_i = W-t$. To avoid ambiguity at equality and maintain complementarity, the only consistent symmetric placement of the decision boundary is $t=W/2$. Any asymmetric choice would violate $f(x)=1-f(\bar x)$ for some $x$.
Thus we eliminate $t$ and obtain:
$$ \sum_{i\in S_k} w_i \ge \frac{1}{2}\sum_{i=1}^n w_i, \quad \sum_{i\in T_j} w_i \le \frac{1}{2}\sum_{i=1}^n w_i. $$
This is now a homogeneous feasibility system in $w$.
4. Correct formulation of majority representation size
A majority representation corresponds to integer weights with threshold exactly half the total weight:
$$ f(x)=1 \iff \sum_i w_i x_i \ge \frac{W}{2}, \quad W=\sum_i w_i. $$
The “size” of the majority representation is $W$, the total number of votes.
5. Fixing the scaling problem (core correction)
The previous flaw was scale invariance: if $w$ is feasible then $\alpha w$ is feasible.
To obtain a meaningful optimization, we introduce a normalization constraint.
A natural normalization for majority representations is:
$$ \sum_{i=1}^n w_i = 1. $$
Under this normalization, $W=1$ and the threshold is fixed to $t=\tfrac{1}{2}$. The system becomes:
For all $k$:
$$ \sum_{i\in S_k} w_i \ge \frac{1}{2}, $$
for all $j$:
$$ \sum_{i\in T_j} w_i \le \frac{1}{2}, $$
$$ \sum_{i=1}^n w_i = 1,\quad w_i\ge 0. $$
This is now a bounded polytope and standard linear programming applies.
6. Minimizing majority representation size
To minimize integer majority size, we proceed in two steps.
6.1 Rational LP solution
Solve the normalized LP above. If it is infeasible, $f$ is not a threshold function.
If feasible, obtain a rational solution $w_i$.
6.2 Scaling to integer majority weights
Convert $w$ to integer weights by clearing denominators:
$$ \tilde w_i = D w_i $$
for a common denominator $D\in\mathbb{Z}_{>0}$. Then:
$$ \sum_i \tilde w_i = D. $$
Thus the size of the majority representation is proportional to $D$.
6.3 Minimization principle
Minimizing majority size is equivalent to minimizing the sum of integer weights, which corresponds to minimizing the denominator needed to realize a feasible rational point of the normalized polytope.
Therefore the correct optimization problem is:
$$ \text{minimize } D \quad \text{such that } w_i=\frac{\tilde w_i}{D} \text{ satisfies the normalized LP}. $$
This is an integer linear optimization problem over the feasible polytope.
7. Final conclusion
- Construct minimal 1-inputs $S_k$ and minimal 0-inputs $T_j$ via dual prime implicants.
- Solve the LP:
$$ \sum_{i\in S_k} w_i \ge t,\quad \sum_{i\in T_j} w_i \le t,\quad w_i\ge 0. $$
- For self-dual functions, enforce $t=W/2$.
- Normalize by $\sum_i w_i=1$ to remove scale invariance.
- Check LP feasibility to decide thresholdness.
- Minimize majority size by minimizing the integer scaling factor of a rational feasible solution.
This fully corrects the earlier gaps: it justifies the extremal set reduction, clarifies dual use, resolves the symmetry argument for self-duality, and fixes the optimization by removing scale invariance through normalization.