TAOCP 7.1.1 Exercise 104
The solution proceeds from the method of Exercise 103: a threshold function f(x)=1 \quad \Longleftrightarrow \quad \sum_i w_i x_i \ge t is converted into a majority function by embedding it into an eq...
Exercise 104. [25] Apply the method of exercise 103 to find the shortest representations of the following threshold functions as majority functions: (a) $\langle x_1 x_2 x_3 x_1^2 x_2^2 x_3^2 x_4^2\rangle$; (b) $\langle x_1 x_2 x_3 x_4\rangle_t$, for $0 \le t \le 16$ (17 cases); (c) $\langle x_1^4 x_2^3 x_1^3 x_2^3 x_3^3 x_4^2 x_5^2 x_6^2 x_7^2 x_8^2\rangle$.
Verified: no
Solve time: 8m17s
The solution proceeds from the method of Exercise 103: a threshold function
$$ f(x)=1 \quad \Longleftrightarrow \quad \sum_i w_i x_i \ge t $$
is converted into a majority function by embedding it into an equivalent unweighted threshold of the form “at least half of the total weight.” The construction uses duplication of variables (to represent weights) together with a possible padding of fixed 1s (or equivalently fixed 0s) so that the majority threshold becomes exact.
Let $W=\sum_i w_i$. A majority representation must satisfy
$$ f(x)=1 \quad \Longleftrightarrow \quad S(x)+k \ge \frac{W+k}{2}, $$
where $S(x)$ is the original weighted sum and $k$ is the number of added constants equal to $1$. Solving,
$$ S(x)\ge t \quad \Longleftrightarrow \quad S(x)+k \ge \frac{W+k}{2} \quad \Longleftrightarrow \quad k = 2t - W. $$
If $k<0$, we instead interpret this as removing slack by adding $|k|$ constant 0 inputs, which do not affect the sum but increase the majority size. The shortest representation is obtained by minimizing $|k|$, hence by choosing the smallest adjustment to balance the inequality.
(a) $\langle x_1 x_2 x_3 x_1^2 x_2^2 x_3^2 x_4^2\rangle$
First compute weights:
$$ w_1=3,\quad w_2=3,\quad w_3=3,\quad w_4=2, \qquad W=11. $$
This notation corresponds to the standard threshold interpretation of the multiset. For a majority representation, we balance to total size $W+k$ with threshold $(W+k)/2$. The minimal adjustment is obtained by taking
$$ k = 2t - W. $$
In this case the expression is already intended as a balanced majority form, so we take $t=\lceil W/2\rceil=6$. Then
$$ k = 2\cdot 6 - 11 = 1. $$
Thus the shortest majority representation is obtained by adding one constant-1 input:
$$ \langle x_1 x_2 x_3 x_1^2 x_2^2 x_3^2 x_4^2, 1\rangle. $$
No smaller adjustment can balance the parity gap $11$ to an even total, so one added 1 is optimal.
(b) $\langle x_1 x_2 x_3 x_4\rangle_t,\quad 0\le t\le 16$
This is the unweighted threshold on four variables, so
$$ W=4,\quad S(x)=x_1+x_2+x_3+x_4. $$
We convert to majority by adding $k$ constant 1s so that
$$ t = \frac{4+k}{2} - k = \frac{4-k}{2}, $$
which rearranges to the standard condition
$$ k = 2t - 4. $$
Hence the shortest representation depends on the sign of $k$.
Case 1: $t=0,1,2$
Then $k \le 0$. We add $|k|$ constant 0 inputs. The representation is
$$ \langle x_1,x_2,x_3,x_4,0,\dots,0\rangle, \quad \text{with } |2t-4| \text{ zeros}. $$
Case 2: $t=2$
Here $k=0$, so the function is already a pure majority:
$$ \langle x_1,x_2,x_3,x_4\rangle. $$
Case 3: $t=3,4,5,6,7,8,9,10,11,12,13,14,15,16$
Here $k>0$. We add $k=2t-4$ constant 1 inputs:
$$ \langle x_1,x_2,x_3,x_4,\underbrace{1,\dots,1}_{2t-4}\rangle. $$
This yields a majority threshold at exactly half of the enlarged multiset. No smaller construction is possible because any majority representation must have even total size, and the parity correction is uniquely determined by $2t-W$.
(c) $\langle x_1^4 x_2^3 x_1^3 x_2^3 x_3^3 x_4^2 x_5^2 x_6^2 x_7^2 x_8^2\rangle$
First combine weights:
$$ w_1=7,\quad w_2=6,\quad w_3=3,\quad w_4=w_5=w_6=w_7=w_8=2. $$
So
$$ W = 7+6+3+5\cdot 2 = 26. $$
We convert to a majority function by choosing $k$ such that
$$ k = 2t - 26. $$
As in Exercise 103, the shortest representation is achieved by minimizing $|k|$, i.e. choosing the closest balanced majority form. The natural balanced threshold is
$$ t=\lceil 26/2\rceil=13, $$
giving
$$ k = 2\cdot 13 - 26 = 0. $$
Hence this representation is already perfectly balanced, and no padding is needed. Therefore the shortest majority representation is simply the multiset itself:
$$ \langle x_1^7 x_2^6 x_3^3 x_4^2 x_5^2 x_6^2 x_7^2 x_8^2\rangle. $$
Final summary
- (a) Add one constant $1$.
- (b) Add $|2t-4|$ constants: zeros if $t<2$, ones if $t>2$, none if $t=2$.
- (c) Already balanced; no additional literals are required.
Each result follows from enforcing equality between the original threshold and the majority cutoff after minimal padding, which is exactly the optimization criterion from Exercise 103.