On the Decomposability of NC and AC
Christopher Wilson
Committee:
Technical Report(Nov 1988)
Keywords:

It is shown for rationals a,b ≥ 1 that NCaNCb = NCa+b-1. As a consequence, if, for some k ≥ 1 and ε > 0, NCk = NCk+ε, then NCk = NC. A similar development can be applied to circuits with unbounded fan-in. It is seen that ACaACb = ACa+b, ACaNCb = NCa+b and NCaACb = ACa+b-1. This shows for a ≥ 0 and b ≥ 1 that ACaACb = NCa+1ACb and ACaNCb = NCa+1NCb. We then construct an oracle A for which ∀k, NCkAACkA and, in fact ACkA - NCk+εA ≠ ∅ for any ε < 1. Similarly, there is an A so that ∀k and ε < 1, NCk+1A - ACk+εA ≠ ∅, and hence ACkA and NCk+εANCk+1A. Combining, this yields an A such that, for all k and 0 < € < 1, the classes ACkA and NCk+εA are incomparable.