On the Decomposability of $NC$ and $AC$

Abstract

It is shown for rationale $a, b \geq 1$ that $NC_a ^{NC_b} = NC_{a+b-1}$. As a consequence, if, for some $k \geq 1$ and $\epsilon > 0, NC_k = NC_{k+\epsilon}$, then $NC_k = NC$. A similar development can be applied to circuits with unbounded fan-in. It is seen that $AC_a ^{AC_{b}} = AC_{a+b}, AC_a ^{NC_b} = NC_{a+b}$, and $NC_a ^{AC_b} = AC_{a + b - 1}$. This shows for $a \geq 0$ and $b \geq 1$ that $AC_a ^{AC_b} = NC_{a+1}^{AC_b}$ and $AC_a ^{NC_b} = NC_{a+1}^{NC_b}$. An oracle A is constructed for which $\forall k$, $NC_k ^A \subset AC_k ^A $ and, in fact, $AC_k ^A - NC_{k+\epsilon }^A \neq \phi$ for any $\epsilon < 1$. Similarly, there is an A so that $\forall k$ and $\epsilon < 1$, $NC_{k+1} ^A - AC_{k+\epsilon }^A \neq \phi $, and hence $AC_k ^A \subset NC_{k+1} ^A$ Combining, this yields an A such that, for all k and $0 < \epsilon < l$, the classes $AC_k ^A $ and $NC_{k+\epsilon} ^A$ are incomparable.