56 Ω Balancing

$\Omega$-balancing

Let us write $\Delta =\{0,1,\delta \}$ for the complete basis containing the Boolean constants $0,1$ and the function $\delta :\{0,1{\}}^3\to \{0,1\}$ given by:

$$\delta (x,y,z):=(\neg x\wedge y)\vee (x\wedge z)$$

Theorem (Spira balancing)

Let $\Omega$ be a complete basis: For every $\Omega$ formula A of size $n$ there is a logically equivalent $\Delta$ formula A’s s.t. $|A^{\prime }|=n^{(O(1))}$ and $depth(A^{\prime })=O(\log n)$.

Proof of $\Omega$ balancing: construction

We proceed by induction on $n$. Let A be a $\Omega$-formula and let B be a distinguished sub-formula of A s.t. $\frac{1}{3}|A|<|B|\le \frac{2}{3}|A|$.
Write $A=C(B)$, so that also $\frac{1}{3}|A|<|C(x)|\le \frac{2}{3}|A|$.
We now have $A$ is logically equivalent to the $\Delta$ formula

$$C(b)⟺\delta (B^{\prime },C(0{)}^{\prime },C(1{)}^{\prime })$$

where $B^{\prime },C(0{)}^{\prime },C(1{)}^{\prime }$ are obtained by the inductive hypothesis