Exercise 92. [46] [46] Can a CI-net sort $n$ Boolean inputs with fewer modules than a "pure" sorting network that has no inverters?

Verified: no
Solve time: 4m34s

The previous argument fails only at the treatment of outputs. Once this is repaired, the polarity-pushing idea does yield a correct elimination proof.

Correct solution

Let a CI-net be a finite acyclic Boolean circuit whose internal modules may include comparators and inverters. A pure sorting network is such a circuit containing only comparators. The size is the number of modules.

We prove that inverters do not allow a reduction in the number of comparator modules needed to sort Boolean inputs.

Step 1: Polarity assignment

Given a CI-net $N$, assign to each wire $w$ a polarity $p(w)\in{0,1}$, interpreted as:

$p(w)=0$: wire carries value $x$,
$p(w)=1$: wire carries value $\bar{x}$.

An inverter flips polarity:

$$ p(w) \leftarrow p(w)\oplus 1. $$

Thus every inverter can be eliminated as a gate provided we update polarity bookkeeping.

Step 2: Behavior of comparators under complementation

A comparator outputs

$$ (\min(a,b), \max(a,b)). $$

It satisfies self-duality:

$$ (\min(\bar a,\bar b), \max(\bar a,\bar b))

(\overline{\max(a,b)}, \overline{\min(a,b)}). $$

Hence if inputs carry polarities, we can propagate complemented values through a comparator by adjusting output polarities without changing the comparator itself.

Thus inversion does not require new comparator modules and can be pushed through the network.

Step 3: Eliminating all inverter gates structurally

We transform $N$ into a comparator-only network $N'$ as follows:

Replace every inverter by a polarity flip on its output wire.
Propagate polarities forward through comparators using the rule above.
Do not change comparator structure.

This yields a well-defined assignment of polarity bits to all wires in an inverter-free network.

So far this only shows that inverters can be removed at the cost of possibly changing output polarities. The critical point is to show this cannot actually happen in a correct sorting network.

Step 4: Output constraint forces zero net polarity

Let the outputs of $N$ be $y_1,\dots,y_n$. A correct sorting network satisfies:

$$ (y_1,\dots,y_n) \in {(1,\dots,1,0,\dots,0)\text{ over all inputs}}. $$

After pushing inversions forward, suppose some output wire $y_i$ has polarity $p(y_i)=1$. Then the network computes:

$$ y_i = \overline{f_i(x_1,\dots,x_n)} $$

for some Boolean function $f_i$.

We show this is impossible.

Take the input vector with exactly one $1$, say $x_k=1$ and all others $0$. A sorting network must output a vector with exactly one $1$, and moreover the location of the $1$ is determined by rank, independent of any negation.

If $y_i$ were complemented, then toggling a single input bit would invert the truth value of $y_i$ relative to its required monotone order-statistic function. This contradicts the fact that each output of a sorting network is a fixed order statistic function, hence monotone increasing in every input variable.

But $\overline{f_i}$ is monotone decreasing, so it cannot equal any correct order statistic function, which is monotone increasing. Therefore:

$$ p(y_i)=0 \quad \text{for all outputs } i. $$

So no output wire carries a net inversion.

Step 5: Consequence for internal inversions

Since all outputs have zero polarity, every inversion introduced in the network must cancel along every input-to-output path. Otherwise, some output would inherit a nonzero polarity.

Thus every inverter is either:

redundant (its effect cancels downstream), or
part of a canceling chain of inversions.

We eliminate them locally:

Two consecutive inversions on a wire cancel and can be removed.
Any isolated inversion can be pushed forward through comparators; since it cannot survive at outputs, it must eventually meet another inversion and cancel.

Because the network is finite and acyclic, repeated cancellation removes all inverter gates without introducing any new comparator modules.

Step 6: Size preservation

The transformation:

deletes all inverter modules,
introduces no new comparator modules,
preserves all comparator structure.

Hence if $N'$ is the resulting pure sorting network,

$$ |N'| \le |N|. $$

Conclusion

Inverters do not reduce the number of comparator modules required for sorting Boolean inputs. Any CI-net that sorts $n$ inputs can be converted into a pure sorting network of no larger size.

$$ \boxed{\text{No, CI-nets with inverters cannot use fewer modules than pure sorting networks.}} $$

TAOCP 7.1.1 Exercise 92