NONDETERMINISTIC NC1 COMPUTATION

We define the counting classes #NC1, GapNC(1), PNC1, and C=NC1. We pro ve that boolean circuits, algebraic circuits, programs over nondetermi nistic finite automata, and programs over constant integer matrices yi eld equivalent definitions of the latter three classes. We investigate closure properties. We observe that #NC1 subset of or equal to #L, th at PNC1 subset of or equal to L, and that C=NC1 subset of or equal to L. Then we exploit our finite automaton model and extend the padding t echniques used to investigate leaf languages, Finally, we draw some co nsequences from the resulting body of leaf language characterizations of complexity classes, including the unconditional separations of ACC( 0) from MOD-PH and that of TC0 from the counting hierarchy. Moreover, we obtain that if dlogtime-uniformity and logspace-uniformity for AC(0 ) coincide then the polynomial time hierarchy equals PSPACE. (C) 1998 Academic Press.