53 Ω Circuits

Definition

Let $\Omega$ be as basis. An $\Omega$-circuit is defined just like a Boolean Circuit, except with (non-source) nodes labelled by arbitrary elements.
$f:\{0,1{\}}^n\to \{0,1\}$ of $\Omega$, with precisely $n$ incoming edges.
The depth of an $\Omega$ circuit is the length of the longest path from a source to the sink.
The size of an $\Omega$ circuit is its number of nodes.

The change-of-bias theorem

Theorem

Let ${\Omega }_1$ and ${\Omega }_2$ be two complete bases. Then for any ${\Omega }_1$-circuit $C_1$ there is an ${\Omega }_2$ circuit $C_2$ computing the same boolean function with:

• $|C_2|=O(|C_1|)$ and
• depth$(C_2)$ = O(depth($C_1$))

Proof Sketch

For each element $f_i\in {\Omega }_1$ let $F_i$ be an ${\Omega }_2$ circuit of size $s_i$ and depth $d_i$ computing $f_i$. Let s = ${\max }_i{s}_i$ and $d={\max }_i{d}_i$.
Now construct $C_2$ by replacing each non-source node labelled $f_i$ by the ${\Omega }_2$ circuit $F_i$. We have $|C_2|\le s(C_1)$ and $depth(C_2)\le d\cdot depth(C_1)$

Example

From $\{0,1,MA{J}^3\}$ to $\{\neg ,\vee ,\wedge \}$

• ${\Omega }_1$ = $\{0,1,MA{J}^3\}$
• ${\Omega }_2$ = $\{\neg ,\vee ,\wedge \}$

${\Omega }_2$ definitions

• 0 $⟺$ $x\wedge \neg x$
• 1 $⟺$ $x\vee \neg x$
• $MA{J}^3(x,y,z)⟺(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)$

From $\{\vee ,\wedge \}$ to $\{0,1,MA{J}^3\}$

• ${\Omega }_1$ = $\{\vee ,\wedge \}$
• ${\Omega }_1$ = $\{0,1,MA{J}^3\}$

${\Omega }_2$ definitions

• $A\vee B⟺MA{J}^3(A,B,1)$
• $A\wedge B⟺MA{J}^3(A,B,0)$